Инвариант. Решение олимпиадных задач
Задача Мише учитель математики поставил в дневник отметку «2». Миша, желая скрыть от мамы данный факт, порвал свой дневник на 4 части. Этого ему показалось мало, поэтому некоторые из этих частей (может быть и не все) он порвал на 4 части и так далее. Мама нашла 20 «кусочков» дневника. Все ли куски нашла мама? Решение: Для того, чтобы решить задачу, необходимо ответить на вопрос: «Какое число обрывков могло получиться?» Сначала Миша порвал дневник на 4 части. Если он порвал на 4 части один из четырех кусочков, то их станет 4+ 3 = 7. Если Миша и дальше будет рвать кусочки на 4 части, то их будет получаться 4 +6 = 10, 4 + 9 = 13, 4 + 12 = 16, 4 + 15 =19, 4 +18 =22 и так далее. Таким образом, кусочков может быть 4, 7, 10, 13, 16, 19, 22, … Значит, мама нашла не все кусочки. Можно заметить, что при делении каждого из этих чисел на 3 получается остаток 1. В данной задаче в качестве инварианта выступил остаток от деления на 3.