Олимпиадная задача про автоматы и карточки с числами — 7–9 класс

Попробуем промоделировать сам процесс решения задачи.Итак, внешний вид задачи: дан набор разрешенных операций и нас просят выяснить, можно ли из одной карточки получить другую - наталкивает нас на то, что нужно искать инвариант. Начнем поиск.1-я операция: (a, b) -> (a + 1, b + 1). Что же не меняется при этой операции? Ну, конечно же, разность чисел на карточке: (a + 1) - (b + 1) = a - b. Но вот уже 2-я операция меняет разность: a/2 - b/2 = (a - b)/2 - она делит ее пополам. 3-я операция складывает эти разности: a - c = (a - b) + (b - c).Все это приводит нас к мысли, что, видимо, инвариантом является не сама разность, а... что же? Что можно сделать с этим числом? Вполне возможно, что ответ на этот вопрос не сразу придет вам на ум. Ну что же, займемся небольшим исследованием. Наудачу попробуем получить какие-то карточки из данной:

(5, 19) -> (6, 20) (6, 20) -> (3, 10) (3, 10) -> (20, 27) (6, 20), (20, 27) -> (6, 27) Пока хватит. Теперь уже можно посмотреть на плоды наших трудов. Мы имеем набор карточек: (5, 19), (6, 20), (3, 10), (20, 27), (6, 27). Вычислим для них разность чисел на карточке и получим набор чисел: 14, 14, 7, 7, 21. Тут, конечно, мы сразу догадались, что нужно доказывать! Конечно же то, что наша разность a - b всегда будет делиться на 7. Доказывается это очень просто, стоит только еще раз посмотреть, что происходит с разностью при разрешенных операциях (см. выше). Но у той карточки, которую нам хочется получить - (1, 1988) - разность чисел равна 1 - 1988 = -1987 и на 7 не делится. Задача решена.