Question

Двое по очереди ломают шоколадку 6 × 8. За ход разрешается сделать прямолинейный разлом любого из кусков вдоль углубления. Проигрывает тот, кто не сможет сделать ход. Кто выиграет при правильной игре, тот, кто делает первый или второй ход? Вечером голова вообще не пашет.

Answer 1

Решение

Основное соображение: после каждого хода количество кусков увеличивается ровно на 1.

Сначала был один кусок. В конце игры, когда нельзя сделать ни одного хода, шоколадка разломана на маленькие дольки. А их 48! Таким образом, игра будет продолжаться ровно 47 ходов. Последний, 47-й ход (так же, как и все другие ходы с нечетными номерами) сделает первый игрок. Поэтому он в этой игре побеждает, причем независимо от того, как будет играть.

Answer 2

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

В данном случае можно показать, что при правильной игре первый игрок всегда выигрывает. Для этого мы можем использовать следующую минимаксную стратегию:

1. Первый игрок делает первый ход в центре шоколадки, разрезая ее на две равные половины 3 × 8.
2. Независимо от того, какой ход сделал второй игрок, первый игрок всегда делает ход, который разрезает его кусок на две равные половины по одному измерению, оставляя второму игроку неравную часть.
3. Если второй игрок делает ход, который разрезает его кусок на две равные половины по одному измерению, то первый игрок делает ход, который разрезает его кусок на две равные половины по другому измерению, оставляя второму игроку неравную часть.

С помощью этой стратегии первый игрок всегда может гарантировать, что у него будет кусок шоколадки, который больше, чем кусок, оставшийся второму игроку. Таким образом, первый игрок выиграет игру, если будет играть правильно.