Question

ДАЮ 100 БАЛЛОВ

На доске 5×5 отмечены центры всех 25 клеток. Доску разбивают на части прямолинейными разрезами, не проходящими через отмеченные точки, так, чтобы в каждой из них было не более одного центра клетки. Какого наименьшего числа разрезов для этого хватит?


(Могу также дать ответ на любую другую задачу олимпиады)

Answer 1

Ответ:8

Пошаговое объяснение:

Докажем, почему нельзя меньше чем 8 разрезами. К краю доски прилегает 16 клеток и их центров. Соединим эти центры по периметру 16-ю отрезками. Один разрез может пересечь максимум 2 отрезка (не считаем, когда разрез прошёл по концу отрезка, т.е. через центр клетки, что нельзя по условию). Тогда, т.к. разрезов 7, то разрезаны будут максимум 14 отрезков --> останется один не разрезанный отрезок --> но он соединяет 2 центра клеток, а значит эти центры будут в одной части. Противоречие. Нужно как минимум 8.

Пример:

Можно разрезать по внутренним вертикалям и горизонталям квадрата 5*5, их как раз 4+4=8.