На шахматной доске 25 х 36 королю разрешено ходить вправо, вверх, вправо-вверх по диагонали или вправо-вниз по диагонали. Чтобы доказать, что он может сделать лишь конечное число ходов, можно рассмотреть полуинвариант. Пронумеруем столбцы слева направо, а строки - снизу вверх.

Решение:

Для решения этой задачи используется понятие полуинварианта. Будем считать, что каждый ход короля увеличивает значение некоторой величины. Если эта величина ограничена сверху, то общее число ходов также будет ограничено.

Занумеруем столбцы слева направо числами от 1 до 36, а строки снизу вверх числами от 1 до 25.

Положение короля на доске можно определить парой чисел \((c, r)\), где \(c\) — номер столбца, а \(r\) — номер строки.

Рассмотрим значение \( v = c + 2r \). При каждом ходе короля будем анализировать, как изменяется это значение.

• Ход вправо: \((c, r) \to (c+1, r)\). Новое значение: \(v' = (c+1) + 2r = (c + 2r) + 1 = v + 1\). Значение увеличивается на 1.
• Ход вверх: \((c, r) \to (c, r+1)\). Новое значение: \(v' = c + 2(r+1) = c + 2r + 2 = v + 2\). Значение увеличивается на 2.
• Ход вправо-вверх по диагонали: \((c, r) \to (c+1, r+1)\). Новое значение: \(v' = (c+1) + 2(r+1) = c+1 + 2r+2 = (c + 2r) + 3 = v + 3\). Значение увеличивается на 3.
• Ход вправо-вниз по диагонали: \((c, r) \to (c+1, r-1)\). Новое значение: \(v' = (c+1) + 2(r-1) = c+1 + 2r-2 = (c + 2r) - 1 = v - 1\). Значение уменьшается на 1.

Мы видим, что при некоторых ходах значение \(v\) увеличивается, а при ходе вправо-вниз по диагонали — уменьшается.

Для доказательства конечного числа ходов нам нужно выбрать такое значение, которое при каждом ходе будет увеличиваться. Рассмотрим другое значение: \( w = 2c + r \).

• Ход вправо: \((c, r) \to (c+1, r)\). Новое значение: \(w' = 2(c+1) + r = 2c + 2 + r = (2c + r) + 2 = w + 2\). Значение увеличивается на 2.
• Ход вверх: \((c, r) \to (c, r+1)\). Новое значение: \(w' = 2c + (r+1) = (2c + r) + 1 = w + 1\). Значение увеличивается на 1.
• Ход вправо-вверх по диагонали: \((c, r) \to (c+1, r+1)\). Новое значение: \(w' = 2(c+1) + (r+1) = 2c+2 + r+1 = (2c + r) + 3 = w + 3\). Значение увеличивается на 3.
• Ход вправо-вниз по диагонали: \((c, r) \to (c+1, r-1)\). Новое значение: \(w' = 2(c+1) + (r-1) = 2c+2 + r-1 = (2c + r) + 1 = w + 1\). Значение увеличивается на 1.

Таким образом, при любом допустимом ходе значение \(w = 2c + r\) всегда увеличивается. Это означает, что король не может сделать бесконечное число ходов, так как значение \(w\) никогда не вернется к своему предыдущему состоянию, а максимальное значение \(w\) ограничено размерами доски (максимум \(c=36, r=25\), тогда \(w_{max} = 2 \times 36 + 25 = 72 + 25 = 97\)).

Ответ: Число ходов короля конечно, так как при каждом ходе увеличивается полуинвариант \( w = 2c + r \).