Question

Из доски 9×9 вырезали 5 клеток, отмеченных на рисунке серым. За один ход из оставшейся доски можно вырезать две клетки, соседние по диагонали. Какое наименьшее количество ходов необходимо сделать, чтобы из оставшейся части доски нельзя было вырезать прямоугольник 1×4? о о о о о о о о х о о о о о о о о о о о о о о о х о о о о о о о о о о о о о о о х о о о о о о о о о о о о о о о х о о о о о о о о о о о о о о о х о о о о о о о о

Answer 1

Ответ:

8

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

1. Начертим доску и обозначим напротив каждой строки или столбца, сколько клеток нужно вырезать из него, чтобы не оставить ни одной последовательности из 4 клеток. Получается, что в каждом направлении нужно вырезать 16 клеток. Делая это экономно, мы обеспечим такой вырезание, что клетка, разбивающая последовательность из 4 по горизонтали, будет делать то же самое и по вертикали. Если у нас получится провести ходы именно так, то вырезание 16 клеток займет 8 шагов. Проверим это практически.

2. Точками обозначим клетки, вырезание которых бесполезно для этой цели. Необозначенными остаются "полезные" клетки

3. Таким же образом обозначим клетки, вырезав которые, мы не можем вырезать "полезную" клетку по диагонали от нее.

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

Получится 8 ходов, см. рисунки.

Answer 2

Для решения этой задачи, давайте представим, что наша оставшаяся доска представляет собой сетку 7x7 (удаляем по одному ряду и одному столбцу с каждой стороны, так как прямоугольник 1x4 не поместится в 9x9). Также обратите внимание, что изначально у нас было 81 клетка (9x9), а 5 клеток были вырезаны, поэтому осталось 76 клеток.

Идея решения заключается в том, чтобы делать ходы таким образом, чтобы уменьшить количество клеток до 8 (2x4), но не до 7 (1x7), так как прямоугольник 1x4 поместится в 1x7. Как только у нас останется 8 клеток, нам не удастся вырезать прямоугольник 1x4.

Начнем с оставшейся сетки 7x7 и проделаем несколько ходов:

1. Удалим 2 клетки по диагонали:

   • Итого: 76 - 2 = 74 клетки

2. Удалим еще 2 клетки по диагонали:

   • Итого: 74 - 2 = 72 клетки

3. Удалим еще 2 клетки по диагонали:

   • Итого: 72 - 2 = 70 клеток

4. Удалим еще 2 клетки по диагонали:

   • Итого: 70 - 2 = 68 клеток

5. Удалим еще 2 клетки по диагонали:

   • Итого: 68 - 2 = 66 клеток

Теперь у нас осталось 66 клеток, и мы не можем вырезать прямоугольник 1x4, потому что это количество клеток меньше 8. Поэтому наименьшее количество ходов, которое необходимо сделать, чтобы из оставшейся части доски нельзя было вырезать прямоугольник 1x4, равно 5 ходам.