Question

СРОЧНО!!!!!!! ДАЮ 40 БАЛЛОВ!!!!!!! На доске 5×5 отмечены центры всех 25 клеток. Доску разбивают на части прямолинейными разрезами, не проходящими через отмеченные точки, так, чтобы в каждой из них было не более одного центра клетки. Какого наименьшего числа разрезов для этого хватит?

Answer 1

Ответ:

8

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

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

Пример:

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

Answer 2

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

На доске 5x5 всего 25 клеток, и у каждой из них есть центр. Чтобы добиться того, чтобы в каждой из частей было не более одного центра клетки, нам нужно избегать ситуаций, когда разрез проходит через центр клетки.

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

Чтобы определить минимальное количество разрезов, давайте визуализируем доску и посмотрим, как можно её разделить.

diffCopy code
x | x | x | x | x
--|---|---|---|--
x | x | x | x | x
--|---|---|---|--
x | x | x | x | x
--|---|---|---|--
x | x | x | x | x
--|---|---|---|--
x | x | x | x | x

Мы видим, что можно разделить доску с помощью 4 вертикальных разрезов и 4 горизонтальных разрезов:

diffCopy code
x | x | x | x | x
--|---|---|---|--
x | x | x | x | x
--|---|---|---|--
x | x | x | x | x
--|---|---|---|--
x | x | x | x | x
--|---|---|---|--
x | x | x | x | x

Таким образом, наименьшее количество разрезов, которое позволит разделить доску 5x5 так, чтобы в каждой части было не более одного центра клетки, равно 4 (вертикальных) + 4 (горизонтальных) = 8 разрезов.