Question

На столе лежат карандаши. Двое играющих берут по очереди 1, 2 или 3 карандаша. Проигрывает тот кто вынужден будет взять последний карандаш. А) Как должен играть начинающий игру, чтобы выиграть, если на столе 8 карандашей? Б) Сможет ли первый выиграть при правильной игре второго, если на столе 9 карандашей? В) Сможет ли первый выиграть при правильной игре второго, если на столе 10 карандашей? Г) Как должен играть начинающий, чтобы выиграть, если на столе лежат 15 карандашей?

Answer 1

Тут удобно использовать метод анализа, который получил называние "backtracking" - обратное прослеживание.

Чтобы безусловно выиграть, нужно оставить противнику один карандаш. Следовательно, перед ходом противника должно быть столько карандашей, чтобы противник не смог оставить один карандаш вам. Это возможно, если карандашей будет пять. Тогда, взяв от одного до трех карандашей, противник оставит вам от четырех до двух карандашей и вы всегда сможете оставить ему только один.
Получается, что для выигрыша нужно оставить противнику перед последним ходом один карандаш, перед предпоследним - пять. Разница - четыре карандаша.
Отсюда видна стратегия игры. Нужно брать столько карандашей, чтобы противнику оставалось 1, 5, 9, 13, 17, 21 и т.д. карандашей.
А) Если карандашей 8, мы берем 3 и оставляем 5.
Б) Если карандашей 9, мы заведомо проиграем, поскольку до 5 у нас 4 карандаша (а больше 3 мы не можем взять), а до 9 - 0 (мы должны взять хотя бы 1 карандаш).
В) Если на столе 10 карандашей, мы берем 1 и получаем выигрышное количество 9.
Г) Если карандашей 15, мы берем 2 и получаем выигрышное количество 13.

Answer 2

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

Правило игры: игроки поочередно берут 1, 2 или 3 карандаша. Проигрывает тот, кто берет последний карандаш.

А) Как должен играть начинающий игру, чтобы выиграть, если на столе 8 карандашей?

Если на столе 8 карандашей, начинающий игру может выбрать любое количество карандашей, чтобы сделать общее количество (8) кратным 4 (1 + 2 + 3 = 6, 8 - 6 = 2). Таким образом, начинающий игру всегда может поддерживать на столе количество карандашей, кратное 4. Таким образом, он всегда сможет выиграть, следуя этой стратегии.

Б) Сможет ли первый выиграть при правильной игре второго, если на столе 9 карандашей?

Если на столе 9 карандашей, начинающий игрок может взять 1 карандаш, оставив 8. Независимо от того, сколько карандашей возьмет второй игрок (1, 2 или 3), начинающий игрок всегда сможет взять столько, чтобы на столе оставалось кратное 4 количество карандашей. Таким образом, начинающий игрок также выиграет при правильной стратегии.

В) Сможет ли первый выиграть при правильной игре второго, если на столе 10 карандашей?

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

Г) Как должен играть начинающий, чтобы выиграть, если на столе лежат 15 карандашей?

Если на столе 15 карандашей, начинающий игрок может взять 1 карандаш, оставив 14. Теперь он может следовать стратегии поддержания кратного 4 количества карандашей и всегда выигрывать. Таким образом, начинающий игрок выиграет при правильной стратегии.