Решение задачи 490

Условие:

На луче из клеток есть ладья и король. София играет за ладью, Софья -- за короля, ходят по очереди, ладья не видит короля. Ладья ест короля, если она оказывается с ним на одной клетке. Сможет ли София съесть Софью?

Решение:

Сможет. Пусть луч бесконечен влево, пронумеруем клетки слева направо по порядку натуральными числами.

Всего есть счетное число гипотез:

1) Изначально король стоит в первой клетке
2) Изначально король стоит во второй клетке

....

Будем их по очереди проверять, играем за Софью. Первую гипотезу проверим, встав в первую клетку. Если не нашли, то проверяем вторую. Мы сделали один ход, значит король стоит не правее третьей клетки (в рамках второй гипотезы). Встанем в третью клетку и пойдем налево маленькими шажками до упора. Если вторая гипотеза верна, то мы его поймаем. Если не поймали, то проверяем следующую гипотезу.

В общем случае: пусть проверили первые n гипотез и короля не обнаружили. Проверям (n+1)-ую гипотезу. Пока проверяли первые n гипотез мы сделали m шагов. Значит, если (n+1)-ая гипотеза верна, то король не правее (n+1+m)-ой клетки. Встанем на эту клетку и пойдем налево до конца с шагом один. Если бы (n+1)-ая гипотеза была верна, мы бы съели короля. И так далее.

Таким образом, при любой начальной расстановке фигур игра закончится за конечное число ходов.

Ответ: Сможет.