Задача 110158
|
|
 |
Условие
Даны натуральные числа p<k<n . На бесконечной клетчатой плоскости отмечены некоторые клетки так, что в любом прямоугольнике (k+1)×n ( n клеток по горизонтали, k+1 – по вертикали) отмечено ровно p клеток. Докажите, что существует прямоугольник k×(n+1) (где n+1 клетка по горизонтали, k – по вертикали), в котором отмечено не менее p+1 клетки.Решение
Рассмотрим два прямоугольника: прямоугольник (k+1)×n и прямоугольник k×(n+1), у которых совпадает левая нижняя клетка.Назовем часть прямоугольника (k+1)×n, не покрытую прямоугольником k×(n+1) черной (это полоска 1×n), а часть прямоугольника k×(n+1), не покрытую прямоугольником (k+1)×n, белой (это вертикальная полоска kx1 ). Объединение этих частей назовем конструкцией.
Если в каком-то положении конструкции на плоскости в белую часть попало больше отмеченных клеток, чем в черную, то мы нашли прямоугольник k×(n+1), в котором больше p отмеченных клеток.
Пронумеруем клетки белой полоски сверху вниз. Рассмотрим любую отмеченную клетку и возьмем k конструкций: такую, чтобы наша отмеченная клетка накрывалась первой клеткой белой полоски, такую, чтобы отмеченная клетка накрывалась второй клеткой белой полоски, и т.д. Черные полоски этих конструкций не перекрываются и в объединении дают прямоугольник k×n, т.е. в сумме накрывают не больше p отмеченных клеток. Каждая белая полоска накрывает хотя бы одну отмеченную клетку.
Поскольку k>p , то среди этих конструкций есть такая, у которой белая часть накрывает больше отмеченных клеток, чем черная, что и требовалось.
