Задача 12745 ...

u466325056

08.01.2017

В клетчатом квадрате 105××105 отмечены центры всех единичных квадратиков (всего 11025 точек). Какое наименьшее число прямых, не параллельных сторонам исходного квадрата, нужно провести, чтобы вычеркнуть все отмеченные точки?

SOVA

08.01.2017

★

Проведем все прямые, параллельные одной из диагоналей квадрата и содержащие более одной из отмеченных точек — таких прямых (зеленые прямые на рисунке).
в квадрате со стороной 3 – 3 прямых;
в квадрате со стороной 5 – 7 прямых;
в квадрате со стороной 7 – 11 прямых;
...
в квадрате со стороной 105 – прямых.
Невычеркнутыми остаются две угловые точки. Их можно вычеркнуть, проведя еще одну прямую — другую диагональ (красного цвета).
Тогда
в квадрате со стороной 3 – 4 прямых;
в квадрате со стороной 5 – 8 прямых;
в квадрате со стороной 7 – 12 прямых;
...
в квадрате со стороной 105 – 208 прямых.
Вообще, в квадрате со стороной n
2·(n–2)+2 прямых.

Докажем, что нельзя обойтись меньшим числом прямых.
Рассмотрим центры единичных квадратиков, расположенных по периметру большого квадрата. Прямая, не параллельная стороне квадрата, может вычеркнуть не более двух таких точек.

О т в е т. 208 прямых