Dutch artist Piet Mondrian’s abstract, rectangular paintings inspired mathematicians to create a two-fold challenge. First, we must completely cover a square canvas with non-overlapping rectangles. All must be unique, so if we use a 1x4, we can’t use a 4x1 in another spot, but a 2x2 rectangle would be fine.
Абстрактные прямоугольные картины голландского художника Пита Мондриана вдохновили математиков на создание двойной задачи. Сначала нужно заполнить квадратный холст непересекающимися прямоугольниками, соотношения сторон которых уникальны. То есть если у нас уже есть 1х4, то нельзя в другом месте использовать 4x1.
Let’s try that. Say we have a canvas measuring 4x4. We can’t chop it directly in half, since that would give us identical rectangles of 2x4. But the next closest option - 3x4 and 1x4 - works.
Но можно использовать прямоугольник 2х2. Давайте попробуем. Например, у нас есть поле 4х4. Мы не можем разделить его ровно на два, потому что получим два одинаковых прямоугольника 2х4.
That was easy, but we’re not done yet. Now take the area of the largest rectangle, and subtract the area of the smallest. The result is our score, and the goal is to get as low a score as possible. Here, the largest area is 12 and the smallest is 4, giving us a score of 8.
Тогда решением будут прямоугольники 3х4 и 1х4. Это было легко, но мы ещё не закончили. Теперь возьмём площадь большего прямоугольника и вычтем из него площадь наименьшего. Результат — это разница, и наша цель — получить разницу как можно меньше. Здесь наибольшая площадь равна 12, а наименьшая — 4,
Since we didn’t try to go for a low score that time, we can probably do better. Let’s keep our 1x4 while breaking the 3x4 into a 3x3 and a 3x1. Now our score is 9 minus 3, or 6. Still not optimal, but better.
получим разницу 8. Поскольку мы не пытались найти наименьшую разницу в первый раз, давайте продолжим искать её. Оставим прямоугольник 1х4 и разделим наш 3х4 на 3х3 и 3х1. Теперь наша разница — 9 минус 3, или 6.
With such a small canvas, there are only a few options. But let’s see what happens when the canvas gets bigger. Try out an 8x8; what’s the lowest score you can get?
Всё ещё недостаточно, но уже лучше. На таком маленьком полотне вариантов решения не так много. Но посмотрим, что произойдёт, если взять холст побольше.
Pause here if you want to figure it out yourself.
Попробуйте поле 8х8, какую минимальную разницу вы сможете получить?
Answer in: 3
Остановите видео, если вы хотите решить задачу самостоятельно.
Answer in: 2
Ответ через: 3
Answer in: 1
Ответ через: 2
To get our bearings, we can start as before: dividing the canvas roughly in two. That gives us a 5x8 rectangle with area 40 and a 3x8 with area 24, for a score of 16. That’s pretty bad. Dividing that 5x8 into a 5x5 and a 5x3 leaves us with a score of 10. Better, but still not great. We could just keep dividing the biggest rectangle. But that would leave us with increasingly tiny rectangles, which would increase the range between the largest and smallest.
Ответ через: 1 Чтобы решить, мы можем начать, как и раньше, разделив холст примерно на две части. Это даст нам прямоугольник размером 5x8 с площадью 40 и прямоугольник 3х8 с площадью 24 с разницей между ними 16. Это довольно-таки плохо. Разделив 5x8 на 5x5 и 5x3, мы получим разницу 10. Уже лучше, но всё ещё не идеально. Мы могли бы продолжать делить самый большой прямоугольник. Но тогда мы получили бы крошечные прямоугольники,
What we really want is for all our rectangles to fall within a small range of area values. And since the total area of the canvas is 64, the areas need to add up to that. Let’s make a list of possible rectangles and areas.
что увеличило бы разницу между самым большим и самым маленьким. Что нам нужно, это наименьшая разница площадей между прямоугольниками. А так как общая площадь холста 64, то сумма площадей должна составлять 64.
To improve on our previous score, we can try to pick a range of values spanning 9 or less and adding up to 64. You’ll notice that some values are left out because rectangles like 1x13 or 2x9 won’t fit on the canvas. You might also realize that if you use one of the rectangles with an odd area like 5, 9, or 15, you need to use another odd-value rectangle to get an even sum. With all that in mind, let’s see what works.
Сделаем список возможных прямоугольников и площадей. Чтобы улучшить наш предыдущий результат, мы можем выбрать диапазон значений от 9 и меньше и в сумме составляющих 64. Вы заметите, что некоторые значения пропущены, потому что прямоугольники вроде 1x13 или 2x9 не помещаются на холсте. Вы также можете заметить, что используя прямоугольник с нечётной площадью 5, 9 или 15, придётся взять прямоугольник с нечётной площадью, чтобы получить чётную сумму.
Starting with area 20 or more puts us over the limit too quickly. But we can get to 64 using rectangles in the 14-18 range, leaving out 15. Unfortunately, there’s no way to make them fit. Using the 2x7 leaves a gap that can only be filled by a rectangle with a width of 1.
Имея это в виду, посмотрим, что у нас получится. Начиная с площади 20 или больше, мы слишком быстро выйдем за пределы. Но мы можем получить 64, используя прямоугольники в диапазоне от 14 до 18, пропустив 15. К сожалению, их никак не разместить на холсте. Используя 2x7, мы получим пробел,
Going lower, the next range that works is 8 to 14, leaving out the 3x3 square. This time, the pieces fit.
который может быть заполнен лишь прямоугольником шириной 1. Двигаясь вниз, получим следующий диапазон от 8 до 14, пропуская квадрат 3х3.
That’s a score of 6. Can we do even better? No. We can get the same score by throwing out the 2x7 and 1x8 and replacing them with a 3x3, 1x7, and 1x6. But if we go any lower down the list, the numbers become so small that we’d need a wider range of sizes to cover the canvas, which would increase the score.
В этот раз кусочки влезают. Получится разница 6. Можем ли мы получить лучший результат? Нет. Мы можем получить тот же результат, выкинув 2x7 и 1x8 и заменив их на 3х3, 1х7 и 1х6. Но если мы продолжим ещё ниже по списку, числа становятся слишком маленькими, так что потребуется больший диапазон для покрытия холста,
There’s no trick or formula here – just a bit of intuition. It's more art than science. And for larger grids, expert mathematicians aren’t sure whether they’ve found the lowest possible scores. So how would you divide a 4x4, 10x10, or 32x32 canvas?
и это увеличит разницу. Здесь нет трюка или формулы — всего лишь немного интуиции. Это больше искусство, чем наука. И для большей сетки эксперты не уверены в том, что они нашли самую маленькую возможную разницу. А как вы разделите холсты 4х4, 10х10
Give it a try and post your results in the comments.
или 32х32?