Выигрышные стратегии в играх с камнями
Двое по очереди берут камни из кучи. Кто взял последний — выиграл. Какие кучи выигрышные — решает рекурсия на Python.
Можно взять {1, 2, 3}П — кратные 4
В — ходящий выигрываетП — ходящий проигрывает
Пять способов показать результат
1
Сначала сыграй
Сыграйте с компьютером. Потом откройте, по какому правилу он побеждает.
Открыть →
2
Лаборатория правил
Меняйте разрешённые ходы — позиции перекрашиваются, период виден сразу.
Открыть →
3
Рекурсия изнутри
Дерево вызовов растёт по шагам. Счётчики «с памятью» и «без» бегут наперегонки.
Открыть →
4
Доказательство в картинках
Две проверки по остаткам доказывают правило для всех n. Окно меток находит период.
Открыть →
5
ЕГЭ на числовой прямой
Задачи 19–21 и демоверсия 2026: метки В1, П1, В2, П2 и стрелки ходов на прямой.
Открыть →
Итоги в цифрах
| Можно взять | Проигрышные позиции (П) | Выигрышный ход |
|---|---|---|
| {1, 2, 3} | n кратно 4 | взять n mod 4 |
| {1, 2, 3, 4} | n кратно 5 | взять n mod 5 |
| {1, 3, 4} | n mod 7 = 0 или 2 | по таблице из 7 остатков; при остатке 3 — два хода |
| {1, 3} | n чётно | любой: исход не зависит от игры |
Ещё результаты
- Запрет брать 2 в {1, 2, 3, 4}: период 5 → 7, позиции меняются в обе стороны (n = 5 был П, стал В).
- Повтор начинается не всегда с нуля: предпериод есть у {2, 4, 7}, а с ходом 1 — у {1, 6, 9}.
- Рекурсия для n = 30 при {1, 2, 3}: без памяти 3 843 200 вызовов, с памятью 67.
- ЕГЭ: 14, 64, 82 (одна куча); 24, 61, 54 (две кучи). Демоверсия 2026: 124; 127 и 128; 132.