Question

Ребята, помогите пожалуйста, не понимаю как решить. Нужно очень срочно. Игра "Ним". Два игрока играют в следующую игру. Перед ними лежат три кучки камней, в одной k камней, в другой m камней, в третьей n камней. За один ход разрешается из любой кучки взять любое количество камней. Проигрывает тот, кто не может сделать очередной ход (т.е камни кончились). Составьте список проигрышных позиций, если: а) k=2, m=4, n=6; б) k=3, m=5, n=7

Answer 1

Ответ:

Ответ. выигрывает первый.

Объяснение:

Пусть первый игрок увеличил на 2 все кучи. Тогда в кучах будет 4, 5, 6 камней. После хода второго возможны следующие комбинации: (6, 7, 8), (8, 5, 6), (4, 10, 6), (4, 5, 12). После этого первому достаточно увеличить вдвое число камней в наибольшей куче и выиграть.

Answer 2

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

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

Давайте рассмотрим два случая:

а) k=2, m=4, n=6:

Найдем ним-сумму для данной позиции:

Ним-сумма = 2 XOR 4 XOR 6 = 2 XOR 4 XOR 6 = 2

Так как ним-сумма не равна 0, то эта позиция является выигрышной для игрока.

б) k=3, m=5, n=7:

Найдем ним-сумму для данной позиции:

Ним-сумма = 3 XOR 5 XOR 7 = 3 XOR 5 XOR 7 = 3

Так как ним-сумма не равна 0, то эта позиция также является выигрышной для игрока.

Таким образом, в обоих случаях позиции являются проигрышными для игроков.