Номер 1334, страница 282 - гдз по математике 6 класс учебник Мерзляк, Полонский

Упражнения. Параграф 46. Координатная плоскость. Глава 4. Рациональные числа и действия над ними - номер 1334, страница 282.

Условие.

1334. В одной кучке лежит 171 камешек, а в другой – 172 камешка. Игроку за один ход разрешается взять любое количество камешков, но только из одной кучки. Проиграет тот, кому будет нечего брать. Кто из двух игроков выиграет при правильной стратегии – тот, кто начинает, или второй игрок?

Решение.

Решение 2.

Кто из двух игроков выиграет при правильной стратегии — тот, кто начинает, или второй игрок?

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

Ключевой характеристикой позиции в игре Ним является её Ним-сумма — результат применения операции побитового «исключающего ИЛИ» (XOR, обозначается как $\oplus$) к количествам камней во всех кучках. Позиция является проигрышной, если её Ним-сумма равна 0, и выигрышной в противном случае.

В начальной позиции у нас две кучки: $n_1 = 171$ и $n_2 = 172$. Вычислим Ним-сумму для этой позиции. Для этого представим числа в двоичной системе счисления:
$171_{10} = 10101011_2$
$172_{10} = 10101100_2$

Теперь найдем их Ним-сумму:
$S = 171 \oplus 172 = 10101011_2 \oplus 10101100_2 = 00000111_2$

Результат в двоичной системе $00000111_2$ соответствует десятичному числу $2^2 + 2^1 + 2^0 = 4 + 2 + 1 = 7$.

Поскольку начальная Ним-сумма $S = 7 \neq 0$, это означает, что исходная позиция является выигрышной для игрока, который ходит первым.

Выигрышная стратегия первого игрока заключается в том, чтобы каждым своим ходом приводить игру в позицию с Ним-суммой, равной нулю. В случае двух кучек это эквивалентно тому, чтобы делать количество камешков в них одинаковым.
Первый игрок может взять 1 камешек из второй, большей кучки (где 172 камешка), чтобы уравнять их количество.
После его хода позиция станет (171, 171). Ним-сумма этой позиции будет $171 \oplus 171 = 0$, что является проигрышной позицией для второго игрока.

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

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

Ответ: При правильной стратегии выиграет тот, кто начинает, то есть первый игрок.