Олимпиадная задача по комбинаторной геометрии и принципу Дирихле для 8–10 класса
Задача
Даны натуральные числа 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 , то среди этих конструкций есть такая, у которой белая часть накрывает больше отмеченных клеток, чем черная, что и требовалось.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь