Математическая задача

Feb 23, 2020 15:29

На столе выкладывается пирамидка из спичек вида
   |
  |||
 |||||
|||||||
4 горизонтальных ряда , в первом ряду 1 спичка, во 2м - 3, ... в 4м - 7 спичек.

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

Решение, предложенное участником форума с псевдонимом X http://bigler.ru/forum_vb/showthread.php?t=29737&page=49
Белые буквы на белом фоне, чтобы увидеть текст, необходимо его "выделить".


В данной конфигурации выигрывает второй.
Можно начать анализировать с конца. Прдположем есть один ряд с А спичками. Если осталась одна - ты проиграл. Если осталось больше - выиграл. Теперь два ряда - А и В спичек. Если А = 1 надо взять В. Если А = 2 и В = 2 то первый проиграл (Если берет 1, то второй берет другой ряд, если 2, то 1 спичку из другого ряда). Если А > 2 и В = 2 тогда первый выигрывает приводя к позиции 2/2.
Таким образом, в конце игры нужно делать так чтобы было нечетное количество рядов с одной спичкой.

Teперь ключевая догадка: если А > 1 и В > 1: запишем их как бинарные числа, и сделаем ХОR* между А и B (т.е если биты разряда разные, то 1, если одинаковые - 0). Если у нас все 0 у нас
"четное" положение, если часть из них 1 - "нечетное".
Нетрудно убедиться что
1) Из четного любой ход приводит к нечетному.
2) Из нечетного всегда можно сделать четное или нечетное, на выбор
3) Эти правила легко обобщаются на любое количество рядов

В начале игры (пока более одного ряда имеет 2 или больше спичек) нужно стремится делать положение противника четным, в конце игры - делать так чтобы оставалось нечетное количество рядов с 1-й спичкой.
Описанная конфигурация (1,3,5,7) - четная, и 3 ряда имеют более 1 спички, т.е. второй игрок выигрывает.

Примечание
*XOR(A,B,C) = XOR(XOR(A,B),C)
Альтернативное определение - если сумма битов четная то 0, если нечетная - 1.
Previous post Next post
Up