|
|
 |
Условие
Два пирата, Билл и Джон, имея каждый по 74 золотые монеты, решили сыграть в такую игру: они по очереди будут выкладывать на стол монеты, за один ход – одну, две или три, а выиграет тот, кто положит на стол сотую по счёту монету. Начинает Билл. Кто может выиграть в такой игре, независимо от того, как будет действовать соперник?
Решение
Если бы пираты имели неограниченное количество монет, то выигрышная стратегия Джона была бы простой: на любой ход Билла ему достаточно дополнять количество монет, которое положил Билл, до четырёх. Действительно, в этом случае, количество монет после каждого хода Джона будет кратно четырём, а 100 делится на 4, поэтому сотую монету Джон смог бы положить своим двадцать пятым ходом. Но у пиратов по 74 монеты, поэтому, если Билл каждый раз будет класть по одной монете, то Джону придётся каждым ходом класть по три монеты, и на двадцать пятый ход Джону монет не хватит. Следовательно, чтобы сохранить такую выигрышную стратегию, Джон должен в какой-то момент положить одну или две монеты. Покажем, что это возможно.
Если первым ходом Билл положит две или три монеты, то Джон сэкономит монеты уже на первом ходу и выиграет. Пусть Билл первым ходом положил одну монету. Тогда Джон в ответ также кладёт одну монету. Далее возможны три случая второго хода Билла.
1) Билл положит одну монету. Тогда Джон также положит одну монету. На столе будет четыре монеты, а дальше Джон сможет применять описанную выше стратегию – ему хватит монет для выигрыша.
2) Билл положит три монеты. Тогда Джон также положит три монеты. На столе будет 8 монет, а Джон уже один раз положил менее трёх монет, поэтому он сможет применить стратегию, описанную выше, и выиграть.
3) Билл положит две монеты. Тогда на столе окажутся четыре монеты. Джон положит одну монету. Билл не должен допустить, чтобы после хода Джона количество монет делилось на 4, поэтому должен положить три монеты. Каждым следующим ходом Джон будет класть одну монету, вынуждая Билла положить три. Но сотую монету Билл положить не сможет, так как для этого ему потребовалось бы 75 монет. Значит, сотую монету положит Джон.
Ответ
Джон.
