|
|
 |
Условие
Есть три печатающих автомата. Первый по карточке с числами a и b выдает карточку с числами a + 1 и b + 1; второй по карточке с четными числами a и b выдает карточку с числами a/2 и b/2; третий автомат по паре карточек с числами a, b и b, c выдает карточку с числами a, c. Все автоматы возвращают заложенные в них карточки. Можно ли с помощью этих автоматов из карточки (5, 19) получить карточку (1, 1988)?Решение
Попробуем промоделировать сам процесс решения задачи.Итак, внешний вид задачи: дан набор разрешенных операций и нас просят выяснить, можно ли из одной карточки получить другую - наталкивает нас на то, что нужно искать инвариант. Начнем поиск.
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 не делится. Задача решена.
Источники и прецеденты использования
| книга | |
| Автор | Генкин С.А., Итенберг И.В., Фомин Д.В. |
| Год издания | 1994 |
| Название | Ленинградские математические кружки |
| Издательство | Киров: "АСА" |
| Издание | 1 |
| глава | |
| Номер | 12 |
| Название | Инвариант |
| Тема | Инварианты |
| задача | |
| Номер | 019 |
