Задача 104121
|
|
 |
Условие
На плоскости даны 16 точек (см. рисунок). а) Покажите, что можно стереть не более восьми из них так, что из оставшихся никакие четыре не будут лежать в вершинах квадрата.
б) Покажите, что можно обойтись стиранием шести точек.
в) Найдите минимальное число точек, которые достаточно стереть для этого.
Решение
в) Всего данные точки образуют 20 квадратов: 9 со стороной 1, 4 со стороной 2, 1 со стороной 3, 4 со стороной и 2 со стороной
Обозначим точки буквами (рис. 1) и подсчитаем вершиной скольких квадратов является каждая точка (рис. 2).
GLOJ – квадрат, поэтому одна из его вершин стерта. Можно считать, что это G или L.
В первом случае "разрушено" ещё 4 квадрата. Осталось 10. Но на каждой из оставшихся точек "сидит" не больше трёх из оставшихся квадратов (рис. 4). Поэтому нужно стереть ещё по крайней мере 4 точки.
Во втором случае "разрушено" ещё 5 квадратов. Осталось 9. Если мы хотим стереть ещё только 3 точки, то на каждой из них должно "сидеть" по 3 квадрата, и все эти 9 квадратов должны быть различны. Но нетрудно проверить, что какие бы три из шести "трёхквадратных" точек мы не взяли (рис. 5), найдутся две из них, являющихся вершинами одного квадрата. Поэтому и в этом случае придется стереть ещё 4 точки.
Ответ
а) Например, см. рис. слева. б) Например, см. рис. справа. в) 6 точек.
