Номер 9, страница 120, часть 2 - гдз по математике 4 класс учебник Дорофеев, Миракова

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

Для решения этой задачи воспользуемся теорией игр, а именно анализом выигрышных и проигрышных позиций. Проигрышная позиция (П-позиция) — это такая позиция, из которой любой ход ведёт в выигрышную позицию. Выигрышная позиция (В-позиция) — та, из которой существует хотя бы один ход, ведущий в проигрышную. Тот, кто начинает свой ход в проигрышной позиции, проигрывает при безошибочной игре соперника. Нам нужно доказать, что начальная позиция является проигрышной.

Обозначим количество конфет в первой кучке как $n_1$, а во второй — как $n_2$. Изначально у нас позиция $(12, 13)$.

Доступные ходы:

1. Съесть 2 конфеты из первой кучки: $(n_1, n_2) \rightarrow (n_1-2, n_2)$. Возможно, если $n_1 \ge 2$.
2. Съесть 2 конфеты из второй кучки: $(n_1, n_2) \rightarrow (n_1, n_2-2)$. Возможно, если $n_2 \ge 2$.
3. Переложить 1 конфету из первой кучки во вторую: $(n_1, n_2) \rightarrow (n_1-1, n_2+1)$. Возможно, если $n_1 \ge 1$.

Игра заканчивается, когда игрок не может сделать ход. Это происходит, когда одновременно не выполняются условия для всех трех ходов, то есть когда $n_1 < 1$ и $n_2 < 2$. Это означает, что $n_1 = 0$ и $n_2$ может быть $0$ или $1$. Таким образом, конечные (проигрышные для того, кто в них оказался) позиции — это $(0, 0)$ и $(0, 1)$.

Рассмотрим, как меняется общее количество конфет $S = n_1 + n_2$ за один ход:

• Ход 1: $S \rightarrow (n_1-2) + n_2 = S-2$.
• Ход 2: $S \rightarrow n_1 + (n_2-2) = S-2$.
• Ход 3: $S \rightarrow (n_1-1) + (n_2+1) = S$.

В начальной позиции $S = 12 + 13 = 25$. Так как любой ход либо не меняет сумму, либо уменьшает её на 2, четность общего количества конфет не меняется. Сумма всегда будет оставаться нечетной. Это означает, что позиция $(0, 0)$, где сумма $0$ (четное число), недостижима. Следовательно, игра может закончиться только в позиции $(0, 1)$.

Теперь найдем инвариант, который позволит нам разделить все позиции на выигрышные и проигрышные. Рассмотрим разность количества конфет во второй и первой кучках по модулю 4: $d = n_2 - n_1 \pmod 4$.

Определим проигрышные и выигрышные позиции:

• Позиция $(n_1, n_2)$ является проигрышной (П-позицией), если $n_2 - n_1 \equiv 1 \pmod 4$.
• Позиция $(n_1, n_2)$ является выигрышной (В-позицией), если $n_2 - n_1 \equiv 3 \pmod 4$.

Проверим, что эта классификация работает:

1. Любой ход из П-позиции ведёт в В-позицию.
Пусть мы находимся в П-позиции, то есть $n_2 - n_1 = 4k + 1$ для некоторого целого $k$. Посмотрим, куда ведут ходы:

• Ход 1 (съесть из первой): новая разность $d' = n_2 - (n_1-2) = (n_2 - n_1) + 2 = (4k+1)+2 = 4k+3$. Позиция стала В.
• Ход 2 (съесть из второй): новая разность $d' = (n_2-2) - n_1 = (n_2 - n_1) - 2 = (4k+1)-2 = 4k-1 = 4(k-1)+3$. Позиция стала В.
• Ход 3 (переложить): новая разность $d' = (n_2+1) - (n_1-1) = (n_2 - n_1) + 2 = (4k+1)+2 = 4k+3$. Позиция стала В.

Действительно, любой возможный ход из П-позиции приводит в В-позицию.

2. Из любой В-позиции есть ход в П-позицию.
Пусть мы находимся в В-позиции, то есть $n_2 - n_1 = 4k + 3$ для некоторого целого $k$. Посмотрим, куда ведут ходы:

• Ход 1 (съесть из первой, если $n_1 \ge 2$): новая разность $d' = n_2 - (n_1-2) = (n_2 - n_1) + 2 = (4k+3)+2 = 4k+5 = 4(k+1)+1$. Позиция становится П.
• Ход 2 (съесть из второй, если $n_2 \ge 2$): новая разность $d' = (n_2-2) - n_1 = (n_2 - n_1) - 2 = (4k+3)-2 = 4k+1$. Позиция становится П.
• Ход 3 (переложить, если $n_1 \ge 1$): новая разность $d' = (n_2+1) - (n_1-1) = (n_2 - n_1) + 2 = (4k+3)+2 = 4k+5 = 4(k+1)+1$. Позиция становится П.

Из В-позиции любой доступный ход ведёт в П-позицию. Так как В-позиция не может быть конечной (конечная позиция $(0,1)$ является П-позицией, как мы увидим ниже), из нее всегда можно сделать ход.

Заключение:

Начальная позиция игры — $(12, 13)$.
Найдем разность: $n_2 - n_1 = 13 - 12 = 1$.
Сравним с 4: $1 \equiv 1 \pmod 4$.
Это означает, что начальная позиция является проигрышной (П-позицией).

Первый игрок вынужден сделать ход из П-позиции, после чего, как мы доказали, он попадёт в В-позицию. Второй игрок, получив В-позицию, всегда может сделать ход, который приведёт игру обратно в П-позицию. Игра будет продолжаться так: первый игрок всегда начинает свой ход в П-позиции, а второй — в В-позиции.

Игра заканчивается в единственно возможной конечной позиции $(0, 1)$. Для нее разность $n_2-n_1=1-0=1$, то есть $1 \equiv 1 \pmod 4$. Конечная позиция является П-позицией. Так как первый игрок всегда оказывается в П-позициях, именно он в итоге окажется в конечной позиции $(0,1)$, не сможет сделать ход и проиграет.

Ответ: Начальная позиция $(12, 13)$ является проигрышной, так как разность $13-12=1$ сравнима с 1 по модулю 4. Любой ход из этой позиции приведет к позиции, где разность сравнима с 3 по модулю 4 (выигрышной). Второй игрок всегда может своим ходом вернуть разность к сравнимой с 1 по модулю 4 (проигрышной для следующего игрока). Поскольку игра конечна и заканчивается в проигрышной позиции $(0,1)$, начинающий игрок, всегда попадающий в проигрышные позиции, в итоге проигрывает.