Применение классических комбинаторных методов к разным задачам → .07 Инвариант

Решение: 1 Заметим, что за каждый ход у нас количество монет увеличивается на . Выпишем первые числа, которые будем получать: . Давайте докажем, что все числа, которые мы можем получить, меняя монеты , нечетные. Действительно, изначально монета одна, число монет нечетное. Каждый раз число монет увеличивается на четное число (на ), поэтому четность количества монет не поменяется и останется нечетной. Так как – четное, его получить нельзя.

Решение 2: Заметим, что количество монет дает остаток при делении на . Действительно, изначально монета одна, а дальше за одну операцию мы прибавляем монеты к нашему количеству, что не меняет остаток при делении на . Но дает остаток ноль при делении на , таким образом, это количество получиться не могло.

Мысль: Если вы сходу не видите какой-то инвариант, но при этом вы можете сделать первые несколько действий – сделайте, не надо просто сидеть и смотреть на задачу:)