На столе лежат две кучки конфет, в первой − 12 конфет, а во второй − 13. Два мальчика играют в такую игру: за ход разрешается либо съесть 2 конфеты из одной кучки, либо переложить 1 конфету из первой кучки во вторую. Проиграет тот, кто не сможет сделать хода. Попробуй доказать, что при данных условиях начинающий всегда проигрывает.

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

Анализ игры

Игра состоит из двух возможных действий:
1. Съесть 2 конфеты из одной кучки.
− В этом случае количество конфет в кучке уменьшается на 2.
2. Переложить 1 конфету из первой кучки во вторую.
− Количество конфет в первой кучке уменьшается на 1, а количество конфет во второй кучке увеличивается на 1.

Игра заканчивается, когда невозможно совершить ни одного хода. Это произойдет, когда:
− В первой кучке окажется меньше 2 конфет, потому что нельзя съесть 2 конфеты из одной кучки, и нельзя переложить конфету во вторую кучку.
− Во второй кучке также окажется меньше 2 конфет.

Цель доказательства

Необходимо показать, что начинающий игрок (первый игрок) всегда проиграет, если оба игрока будут действовать рационально.

Постановка условия выигрыша

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

Математическая модель

Для упрощения анализа введем обозначения:
− $ x $ — количество конфет в первой кучке.
− $ y $ — количество конфет во второй кучке.

Начальное состояние игры:
$$ x = 12, \quad y = 13. $$

Ход 1: Съесть 2 конфеты из одной кучки

Если игрок выберет этот ход:
− В первой кучке будет $ x - 2 $ конфет.
− Во второй кучке останется $ y $ конфет, если конфеты съедены из первой кучки, или $ y - 2 $, если съедены из второй.

Ход 2: Переложить 1 конфету из первой кучки во вторую

Если игрок выберет этот ход:
− В первой кучке будет $ x - 1 $ конфет.
− Во второй кучке будет $ y + 1 $ конфет.

Запрет на ход

Когда ни один из ходов невозможен:
− В первой кучке должно быть $ x < 2 $.
− Во второй кучке должно быть $ y < 2 $.

Инвариант игры

В данной игре введем математическую инвариантную величину, которая остается неизменной вне зависимости от комбинации ходов:
$$ x + y \pmod{3}. $$
Эта величина равна остатку от деления суммы конфет в обеих кучках на 3.

Почему инвариант подходит?

Каждый допустимый ход изменяет сумму конфет $ x + y $:
1. Если съедаются 2 конфеты:
$$ x + y \rightarrow x + y - 2. $$
Вычитание $ 2 $ из суммы конфет сохраняет остаток $ \pmod{3} $.

1. Если одна конфета перекладывается из первой кучки во вторую: $$ x + y \rightarrow x - 1 + y + 1 = x + y. $$ Сумма конфет не меняется.

Таким образом, инвариант $ x + y \pmod{3} $ остается неизменным на протяжении всей игры.

Начальное состояние

В начале игры:
$$ x + y = 12 + 13 = 25. $$
Остаток от деления суммы на 3:
$$ 25 \pmod{3} = 1. $$

Последнее состояние

Игра заканчивается, когда обе кучки содержат меньше 2 конфет:
$$ x < 2, \quad y < 2. $$
Возможные значения $ x $ и $ y $ в конце игры:
$$ x = 0, y = 0; \quad x = 0, y = 1; \quad x = 1, y = 0; \quad x = 1, y = 1. $$
Сумма конфет в каждой из этих ситуаций:
$$ x + y = 0; \quad x + y = 1; \quad x + y = 2. $$
Остаток $ x + y \pmod{3} $ для этих случаев:
$$ 0 \pmod{3}, \quad 1 \pmod{3}, \quad 2 \pmod{3}. $$

Наблюдение

Начальное состояние имеет остаток $ 1 \pmod{3} $. Чтобы доказать, что начинающий игрок проиграет, нужно показать, что любой его ход оставляет противнику состояние с $ 1 \pmod{3} $, а последний ход приводит к состоянию $ 0 \pmod{3} $, в котором ход уже невозможен.

Логика проигрыша первого игрока

Каждый ход сохраняет инвариант $ x + y \pmod{3} $. Поскольку игра начинается с остатка $ 1 \pmod{3} $, последний ход (который приведет к состоянию $ 0 \pmod{3} $) всегда будет сделан вторым игроком. Следовательно, первый игрок проиграет.