На доске 5×5 отмечены центры всех 25 клеток. Доску разбивают на части прямолинейными разрезами, не проходящими через отмеченные точки, так, чтобы в каждой из них было не более одного центра клетки. Какого наименьшего числа разрезов для этого хватит?
Докажем, почему нельзя меньше чем 8 разрезами. К краю доски прилегает 16 клеток и их центров. Соединим эти центры по периметру 16-ю отрезками. Один разрез может пересечь максимум 2 отрезка (не считаем, когда разрез по концу отрезка, т.е. через центр клетки, что нельзя по условию). Тогда, т.к. разрезов 7, то разрезаны будут максимум 14 отрезков --> останется один не разрезанный отрезок --> но он соединяет 2 центра клеток, а значит эти центры будут в одной части. Противоречие. Нужно как минимум 8.
Пример:
Можно разрезать по внутренним вертикалям и горизонталям квадрата 5*5, их как раз 4+4=8. Вот так как-то...
8
Пошаговое объяснение:
Докажем, почему нельзя меньше чем 8 разрезами. К краю доски прилегает 16 клеток и их центров. Соединим эти центры по периметру 16-ю отрезками. Один разрез может пересечь максимум 2 отрезка (не считаем, когда разрез по концу отрезка, т.е. через центр клетки, что нельзя по условию). Тогда, т.к. разрезов 7, то разрезаны будут максимум 14 отрезков --> останется один не разрезанный отрезок --> но он соединяет 2 центра клеток, а значит эти центры будут в одной части. Противоречие. Нужно как минимум 8.
Пример:
Можно разрезать по внутренним вертикалям и горизонталям квадрата 5*5, их как раз 4+4=8. Вот так как-то...