Разделы 
Дополнительно
Задача по математике - 1784
2019-01-20 
Квадратная доска разделена сеткой горизонтальных и вертикальных прямых на $n^2$ клеток со стороной 1. При каком наибольшем $n$ можно отметить $n$ клеток так, чтобы любой прямоугольник площади не менее $n$ со сторонами, идущими по линиям сетки, содержал хотя бы одну отмеченную клетку?
Решение:
Ясно, что если $n$ клеток отмечены так, что выполняется условие задачи, то в каждой строке и в каждом столбце находится ровно одна отмеченная клетка. Считая, что $n \geq 3$ (очевидно, что $n = 2$ - не наибольшее), возьмем строку $A$, в которой отмечена первая клетка, строку $В$, соседнюю с $A$, и строку $C$, соседнюю либо с $A$ (и не совпадающую с $B$), либо с $B$ (и не совпадающую с $A$).
Пусть $b$ - номер отмеченной клетки в строке $В$. Если $b \leq n - \frac{n+1}{2}$, то в строках $A$ и $В$ найдется прямоугольник площади не меньшей $n$, не содержащий отмеченных клеток, следовательно, $n - [\frac{n+1}{2}] < b < [\frac{n+1}{2}] + 2$. Рассмотрим два прямоугольника, образованных пересечением строк $A, В$ и $C$ со столбцами с номерами $2, 3, \cdots, n - [\frac{n+1}{2}]$ и со столбцами с номерами $2 + [\frac{n+1}{2}], ..., n$. В этих прямоугольниках не лежат отмеченные клетки строк $A$ и $В$. Если $n > 7$, то площадь каждого из них не меньше $n$, но строка $C$ содержит лишь одну отмеченную клетку, т. е. один из этих прямоугольников не содержит отмеченных клеток. Итак, мы доказали, что $n \leq 7$. Пример доски $7 \times 7$, удовлетворяющей условию задачи, приведен на рис.
Замечание. При $n = 6$ отметить клетки требуемым образом невозможно, что следует из решения.
Ответ. $n = 7$.
Квадратная доска разделена сеткой горизонтальных и вертикальных прямых на $n^2$ клеток со стороной 1. При каком наибольшем $n$ можно отметить $n$ клеток так, чтобы любой прямоугольник площади не менее $n$ со сторонами, идущими по линиям сетки, содержал хотя бы одну отмеченную клетку?
Решение:
Ясно, что если $n$ клеток отмечены так, что выполняется условие задачи, то в каждой строке и в каждом столбце находится ровно одна отмеченная клетка. Считая, что $n \geq 3$ (очевидно, что $n = 2$ - не наибольшее), возьмем строку $A$, в которой отмечена первая клетка, строку $В$, соседнюю с $A$, и строку $C$, соседнюю либо с $A$ (и не совпадающую с $B$), либо с $B$ (и не совпадающую с $A$).
Пусть $b$ - номер отмеченной клетки в строке $В$. Если $b \leq n - \frac{n+1}{2}$, то в строках $A$ и $В$ найдется прямоугольник площади не меньшей $n$, не содержащий отмеченных клеток, следовательно, $n - [\frac{n+1}{2}] < b < [\frac{n+1}{2}] + 2$. Рассмотрим два прямоугольника, образованных пересечением строк $A, В$ и $C$ со столбцами с номерами $2, 3, \cdots, n - [\frac{n+1}{2}]$ и со столбцами с номерами $2 + [\frac{n+1}{2}], ..., n$. В этих прямоугольниках не лежат отмеченные клетки строк $A$ и $В$. Если $n > 7$, то площадь каждого из них не меньше $n$, но строка $C$ содержит лишь одну отмеченную клетку, т. е. один из этих прямоугольников не содержит отмеченных клеток. Итак, мы доказали, что $n \leq 7$. Пример доски $7 \times 7$, удовлетворяющей условию задачи, приведен на рис.
Замечание. При $n = 6$ отметить клетки требуемым образом невозможно, что следует из решения.
Ответ. $n = 7$.
