Question

На столе лежат камни. Двое игроков по очереди берут со стола3. 4,5 или6 камней. Проигрывает тот, кто не может сделать ход. В частности, игрок, которому достался один камень, проиграл. а) Оцените позиции (от 0 до 31 включительно) - распишите какие номера В (выигрышные), а какие П (проигрышные) б) Является ли позиция 805 проигрышной или выигрышной?

Answer 1

251 выигрышный позиция 0 проигравшая

Answer 2

Для оценки позиций в этой игре можно воспользоваться методом "ним-суммы" (nim-sum), который используется в теории игр для определения выигрышных и проигрышных позиций.

Правила игры:

1. Изначально на столе лежит некоторое количество камней.
2. Игроки поочередно берут от 3 до 6 камней.
3. Проигрывает тот игрок, который не может сделать ход (на столе не осталось камней).

Чтобы оценить позиции, мы будем использовать двоичную запись количества камней в каждой кучке. Позиции будут оцениваться с помощью операции XOR (побитовое исключающее ИЛИ) над двоичными записями количества камней в каждой кучке.

а) Оценка позиций:

• 0000 (0) - П
• 0001 (1) - В
• 0010 (2) - В
• 0011 (3) - П
• 0100 (4) - В
• 0101 (5) - П
• 0110 (6) - П
• 0111 (7) - В
• 1000 (8) - В
• 1001 (9) - П
• 1010 (10) - П
• 1011 (11) - В
• 1100 (12) - П
• 1101 (13) - В
• 1110 (14) - В
• 1111 (15) - П
• 10000 (16) - В
• ...

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

Позиции с нечетным числом единиц в двоичной записи считаются выигрышными (В), а с четным числом единиц - проигрышными (П).

б) Оценка позиции 805:

Для оценки позиции 805 сначала представим ее в двоичной системе счисления:

805 (десятичное) = 1100100101 (двоичное)

Теперь мы можем оценить эту позицию, используя операцию XOR с позициями из пункта а):

1100100101 XOR 0011001111 = 1111101010

Двоичное значение 1111101010 имеет нечетное количество единиц, поэтому позиция 805 считается выигрышной (В).

Итак, позиция 805 является выигрышной.