Областная олимпиада по математике, 2025 год, 10 класс

$A$ и $B$ играют в игру на клетчатой доске $100\times 100$. У каждого игрока есть по фишке. В начале игры фишка игрока $A$ стоит в левом нижнем углу, а фишка игрока $B$ — в правом нижнем углу. Игроки делают ходы по очереди, начинает $A$. За один ход игрок передвигает свою фишку на любую клетку доски, соседнюю по стороне с клеткой предыдущей позиции. Докажите, что игрок $A$ за конечное число ходов сможет добиться того, что в какой-то момент его фишка будет стоять на одной клетке с фишкой игрока $B$, независимо от ходов второго игрока.

Комментарий/решение

Прономеруем столбы от a_{1} до а_{100}, строки она логично с б_{1} до б_{100}. Стратегия выигрыша(выигрыш тот случай когда А становиться на клетку В):Если фишка А стоит на бn строке(n натуральное число от 1 до 100), а фишка В на строке б_{n-1} или б_{n} или б_{n+1} то мы движемся в сторону фишки В(то есть на лево или на право)

А если фишка А стоит на строке бn, и фишка В стоит на строке б_{n-2} или б_{n+2} то мы двигаем фишка на вверх или вниз (смотря где фишка В). Стоит отметить что каждый раз когда фишка B будет упираться в один из сторон, фишка А будет приближаться. И проделывая эти операции мы доберемся до фишки В так как будут моменты когда фишка В будет упираться к одной из сторон доски. И будет момент когда фишка А стоит на клетке а_{99} б_{2} а фишка B стоит на клетке а_{100} б_{1} или момент когда фишка А стоит на а_{99} б_{99} и фишка В стоит на а_{100}. б_{100}, и в обеих этих случаях на следующем ходу игрок А выиграет.

Прономеруем столбы от a_1 до а_100, строки она логично с б_1 до б_100. Стратегия выигрыша(выигрыш тот случай когда А становиться на клетку В):Если фишка А стоит на бn строке(n натуральное число от 1 до 100), а фишка В на строке б_n-1 или б_n или б_n+1 то мы движемся в сторону фишки В(то есть на лево или на право)

А если фишка А стоит на строке б_n, и фишка В стоит на строке б_n-2 или б_n+2 то мы двигаем фишка на вверх или вниз (смотря где фишка В). Стоит отметить что каждый раз когда фишка B будет упираться в один из сторон, фишка А будет приближаться. И проделывая эти операции мы доберемся до фишки В так как будут моменты когда фишка В будет упираться к одной из сторон доски. И будет момент когда фишка А стоит на клетке а_99 б_2 а фишка B стоит на клетке а_100 б_1 или момент когда фишка А стоит на а_99 б_99 и фишка В стоит на а_100. б_100, и в обеих этих случаях на следующем ходу игрок А выиграет.

Решение:

У $A$ две цели чтобы выйграть:

1) Сделать так чтобы после его хода фишки $A$ и $B$ оказались по диагонали внутри квадрата $2$ x $2$. Тогда очевидно что диапазон ходов для $B$ будет сужатся и так как таблица ограничена в конце концов $A$ добъется своего.

2) Сделать так чтобы после хода $A$, фишки $A$ и $B$ лежали на одной строке через одну клетку. В этом случае либо $B$ проиграет сразу либо потихоньку по 1 случаю.

Алгоритм ходов для $A$:

Для $2$ случая нам нужно чтобы после хода $A$ между фишками было нечетное кол-во клеток если они лежат на одной строке. А для $1$ надо чтобы между фишками было четное кол-во клеток если они находят в соседние строках. На других строках они находится не должны иначе если $B$ будет убегать верх или вниз то $A$ будет просто гнаться за ним.

Так как изначально между ними четное кол-во ходов то $A$ движется по строке, и далее:

1) Если $B$ также движется в сторону $A$ по строке то $A$ отвечает тем же ходом.

2) Если $B$ уйдет на соседнюю строку верх или вниз тогда $A$ продолжает идти по своей строке.

3) Если $B$ вернется на строку $A$ тогда $A$ также идет дальше по строке.

Тем самым такими ходами $A$ добъется своего.