|
|
 |
Условие
Все клетки квадратной таблицы n×n пронумерованы в некотором порядке числами от 1 до n². Петя делает ходы по следующим правилам. Первым ходом он ставит фишку в любую клетку. Каждым последующим ходом Петя может либо поставить новую фишку на какую-то клетку, либо переставить фишку из клетки с номером a ходом по горизонтали или по вертикали в клетку с номером большим, чем a. Каждый раз, когда фишка попадает в клетку, эта клетка немедленно закрашивается; ставить фишку на закрашенную клетку запрещено. Какое наименьшее количество фишек потребуется Пете, чтобы независимо от исходной нумерации он смог за несколько ходов закрасить все клетки таблицы?
Решение
n фишек достаточно. Действительно, на каждую строку хватит одной фишки: можно поставить её в клетку строки с минимальным номером, а затем обойти все клетки строки в порядке возрастания номеров.
Покажем, что меньшего числа фишек может и не хватить. Для этого пронумеруем клетки одной диагонали числами 1, 2, ..., n, а остальные клетки нумеруем произвольно. Тогда одна фишка не сможет побывать на двух клетках этой диагонали: если фишка встала на одну её клеток, то следующим ходом она обязана будет пойти на клетку с номером, большим n, и значит, после этого не сможет вернуться на диагональ. Поскольку на каждой клетке диагонали должна побывать фишка, Пете придётся использовать не менее n фишек.
Ответ
n фишек.
