|
|
 |
Условие
На клетчатый лист бумаги размера 100×100 положили несколько попарно неперекрывающихся картонных равнобедренных прямоугольных треугольничков с катетом 1; каждый треугольничек занимает ровно половину одной из клеток. Оказалось, что каждый единичный отрезок сетки (включая граничные) накрыт ровно одним катетом треугольничка. Найдите наибольшее возможное число клеток, не содержащих ни одного треугольничка.
Решение
Положим n = 50. Назовём треугольничек верхним, если он расположен сверху от прямой, содержащей его горизонтальный катет, и нижним иначе. Пронумеруем горизонтальные линии сетки снизу вверх числами от 0 до 2n.
Оценка. Обозначим через uk (соответственно dk) число отрезочков k-й линии, участвующих в верхних (соответственно нижних) треугольничках; тогда
uk + dk = 2n и u0 = d2n = 2n. Кроме того, вертикальные отрезки сетки, расположенные между k-й и (n+1)-й линиями, участвуют ровно в uk + dk+1 треугольничках, так что uk + dk+1 = 2n + 1. Отсюда несложно получить, что dk = k и uk = 2n – k при всех k.
Рассмотрим теперь клетки, расположенные между k-й и (k+1)-й линиями сетки. Хотя бы uk = 2n – k из этих клеток содержат по верхнему треугольнику, и хотя бы dk+1 = k + 1 из них содержат по нижнему. Значит, свободных клеток в этом ряду не больше, чем 2n – max{uk, dk+1}, то есть не больше k при k < n и не больше (2n – 1) – k при k ≥ n. Итого, общее число свободных клеток не больше, чем 2(0 + 1 + … + (n – 1)) = n(n – 1).
Пример. На рисунке показан пример для n = 4. Пример при n = 50 строится аналогично: выделяется "прямоугольник" из клеток со сторонами из n + 1 и n клеток, параллельными диагоналям доски, его клетки красятся в шахматном порядке (так, что угловые клетки прямоугольника – чёрные), и во все чёрные клетки кладётся по два треугольничка (при этом n(n – 1) белых клеток остаются свободными); в оставшихся же четырёх "углах" доски треугольнички кладутся так, что прямой угол треугольника "направлен" в ту же сторону, что и весь "угол".
Ответ
49·50 = 2450 клеток.
