Из доски 9×9 вырезали 5 клеток, отмеченных на рисунке серым. за один ход из оставшейся доски можно вырезать две клетки, соседние по диагонали. какое наименьшее количество ходов необходимо сделать, чтобы из оставшейся части доски нельзя было вырезать прямоугольник 1×4? о о о о о о о о х о о о о о о о о о о о о о о о х о о о о о о о о о о о о о о о х о о о о о о о о о о о о о о о х о о о о о о о о о о о о о о о х о о о о о о о о
8
Пошаговое объяснение:
1. Начертим доску и обозначим напротив каждой строки или столбца, сколько клеток нужно вырезать из него, чтобы не оставить ни одной последовательности из 4 клеток. Получается, что в каждом направлении нужно вырезать 16 клеток. Делая это экономно, мы обеспечим такой вырезание, что клетка, разбивающая последовательность из 4 по горизонтали, будет делать то же самое и по вертикали. Если у нас получится провести ходы именно так, то вырезание 16 клеток займет 8 шагов. Проверим это практически.
2. Точками обозначим клетки, вырезание которых бесполезно для этой цели. Необозначенными остаются "полезные" клетки
3. Таким же образом обозначим клетки, вырезав которые, мы не можем вырезать "полезную" клетку по диагонали от нее.
4. Мы исключили все лишние ходы и теперь можем начинать вырезать клетки в соответствии с числами, которые мы записали на шаге 1.
Получится 8 ходов, см. рисунки.