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

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

Условие.

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

Решение.

Решение 2.

Данная задача является классическим примером комбинаторной игры, известной как игра Ним. Выигрышная стратегия в таких играх определяется с помощью так называемой ним-суммы, которая вычисляется через операцию побитового исключающего "ИЛИ" (XOR, обозначается как $\oplus$) для количеств предметов в каждой кучке.

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

В начальный момент в кучках находится 171 и 172 камешка. Вычислим ним-сумму для этой начальной позиции: $S = 171 \oplus 172$.

Для этого представим числа в двоичной системе счисления:

• $171_{10} = 128 + 43 = 128 + 32 + 11 = 128 + 32 + 8 + 3 = 128 + 32 + 8 + 2 + 1 = 2^7 + 2^5 + 2^3 + 2^1 + 2^0 = 10101011_2$
• $172_{10} = 171 + 1 = 10101100_2$

Теперь выполним операцию XOR над двоичными представлениями этих чисел:

 10101011 (171)⊕ 10101100 (172)----------------- 00000111

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

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

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

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

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

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

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