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