Информация о задаче

Задача 79511

Темы:	[	Разные задачи на разрезания	]
	[	Примеры и контрпримеры. Конструкции	]
	[	Вспомогательная раскраска	]

Сложность: 4+
Классы: 9

Прислать комментарий

Условие

Школьник хочет вырезать из квадрата размером 2n×2n наибольшее количество прямоугольников размером 1×(n + 1). Найти это количество для каждого натурального значения n.

Решение

Площадь квадрата 2n×2n равна 4n², а площадь прямоугольника 1×(n+1) равна n+1. Следовательно, число вырезанных прямоугольников не превосходит $\left[\vphantom{\frac{4n^2}{n+1}}\right.$ ${\frac{4n^2}{n+1}}$ $\left.\vphantom{\frac{4n^2}{n+1}}\right]$ , где [n] — целая часть числа n, то есть наибольшее целое число, не превосходящее n. Заметим, что

$\left[\vphantom{\frac{4n^2}{n+1}}\right.$ ${\frac{4n^2}{n+1}}$ $\left.\vphantom{\frac{4n^2}{n+1}}\right]$ = $\left[\vphantom{{\frac{4(n^2-1)}{n+1}}\relax +{\frac{4}{n+1}}}\right.$ ${\frac{4(n^2-1)}{n+1}}$ + ${\frac{4}{n+1}}$ $\left.\vphantom{{\frac{4(n^2-1)}{n+1}}\relax +{\frac{4}{n+1}}}\right]$ = 4(n − 1) + $\left[\vphantom{\frac{4}{n+1}}\right.$ ${\frac{4}{n+1}}$ $\left.\vphantom{\frac{4}{n+1}}\right]$ .

Следовательно, при n ≥ 4 количество прямоугольников, которые может вырезать школьник, не превосходит 4(n − 1). Способ вырезать 4n − 4 прямоугольников показан на рисунке (для n = 5).

Осталось решить задачу при n ≤ 3. При n = 1 школьник хочет вырезать из квадрата размером 2×2 наибольшее количество прямоугольников размером 1×2. Ясно, что в этом случае ответ 2 (достаточно квадрат разрезать пополам любой из его средних линий).
При n = 2 школьник хочет вырезать из квадрата размером 4×4 наибольшее количество прямоугольников размером 1×3. Так как площадь квадрата равна шестнадцати, а площадь прямоугольника — трём, то можно вырезать не более пяти прямоугольников. Способ вырезать пять прямоугольников показан на рисунке.

При n = 3 школьник хочет вырезать из квадрата размером 6×6 наибольшее количество прямоугольников размером 1×4. Так как площадь квадрата равна 36, а площадь прямоугольника — четырём, то число вырезанных прямоугольников не превосходит девяти. Допустим, школьник смог вырезать девять прямоугольников. Это означает, что ему удалось разрезать квадрат 6×6 на прямоугольники 1×4. Ясно, что линии разреза параллельны сторонам квадрата, то есть каждая клетка полностью лежит в каком-нибудь прямоугольнике. Раскрасим клетки доски 6×6 как показано на рисунке. Так как число клеток цвета 1 не равно числу клеток цвета 2, а каждый прямоугольник 1×4 содержит по одной клетке каждого цвета, то квадрат 6×6 нельзя разрезать на прямоугольники 1×4. Следовательно, число прямоугольников не больше восьми. Способ вырезать восемь прямоугольников изображён на рисунке.

Источники и прецеденты использования


олимпиада
Название	Московская математическая олимпиада
год
Номер	50
Год	1987
вариант
Класс	8
задача
Номер	2