Игра в палочки — олимпиадная тема, которая решается по четкому алгоритму. Это задачи, в которых сформулированы правила игры, а чтобы задача решилась нужно предъявить выигрышную стратегию — план, как гарантированно выиграть вне зависимости от ходов соперника. Выигрышная стратегия может быть только у одно из игроков, но бывают игры с ничейной стратегией, например, крестики-нолики. При этом известно, что игроки играют правильно и стараются победить, а значит не зевают ходы, не ошибаются и не поддаются. 🍉Формулируем решение Первое, что нужно определить — какой игрок может обеспечить победу? В классических задачах на игры есть 2 игрока и только 1 может победить. Если вы определили, что выиграть может первый игрок, то вам нужно описать стратегию. Дети любят говорить "посмотрим по ситуации", но как поступать в разных ситуациях и есть стратегия игры, ее нужно описать для любого хода соперника, даже не логичного. 🔰Условие задачи На столе лежит 20 палочек, за один ход игрок может взять 1 или 2 палочки. Выигрывает тот, кто взял последнюю палочку. ⚡️Процесс решения Если на столе лежит 1 или 2 палочки, то первый игрок их забирает и выигрывает. Если лежит уже 3 палочки, то выигрывает второй игрок, так как одним ходом первый игрок все не возьмет. Если лежит 4 или 5 палочек, то выигрывает первый, так как он может оставить сопернику 3 палочки, которые за один ход соперник взять не сможет. Если палочек 6, то выигрывает второй, потому что как бы не сходил первый, второй ему оставит тройку. Значит для победы второму игроку нужно обеспечить себе целое количество троек, чтобы противник открывал тройку, а мы ее завершали. У нас 20 палочек, и здесь при делении на 3 есть остаток 2. Значит первый игрок может обеспечить себе победу, забрав остаток первым ходом, а на остальные ходы соперника добирать тройку: если второй взял 1 палочку, первый берет 2, если второй взял 2 палочки, первый берет 1. 🦋Делаем последнюю палочку проигрышной Меняем условие. Теперь тот, кто взял последнюю палочку, проигрывает игру. Мы эту палочку называем фу-палочкой, которую никто не хочет брать и мысленно откладываем подальше. И теперь решаем задачу с 19 палочками, кто возьмет последнюю, тот и победил. А значит первый игрок забирает остаток от деления 19 на 3 и использует ту же стратегию добора до тройки. 🌈Общий алгоритм Находим ключевое число, до которого мы будем добирать. Оно определяется максимальным количеством палочек, которые мы можем взять за один ход. Если можно взять 1 или 2 палочки за ход, то ключевое число 3, а если можно брать 1, 2, 3, 4 или 5 палочек, то 6. Определяем фу-палочку. Если выигрывает игрок, который забирает последнюю палочку, то фу-палочки нет. Если тот, кто забирает последнюю палочку проигрывает, то играем с фу-палочкой. Если при делении общего числа хороших палочек на ключевое число есть остаток, то выигрывает первый игрок и первым ходом он забирает этот остаток, а дальше добирает до ключевого числа. Если же остатка нет, то выигрывает второй.