Международный научно-образовательный электронный журнал «образование и наука в XXI веке». Выпуск №10 (том 1)

Упражнение. Докажите, что все белки могут собраться на одной елки тогда и только тогда, 
когда их нечетное число (то есть, для четных чисел - обобщить данное выше решение, для 
нечетных - придумать пример.)
Разность каких-то количеств и набор попарных разностей - тоже типичные 
инварианты. После суммы и произведения следующим делом надо проверять именно 
разности.
Задача 8. Есть три программы. Одна по файлу с числами Х и У создает файл с числами
Х + 1 и У + 1, вторая по файлу с четными числами Х и У создает файл с числами Х/2 и У 
/2, третья по двум файлам с числами Х, У и У, Z создает файл с числами Х, Z. Все старые 
файлы сохраняются. Исходно есть 1 файл с числами (5, 19). Можно ли с помощью этих 
программ получить файл с числами (1, 2004)?
Решение: Где же искать инвариант? С суммой чисел в файле как-то сложно, потому что 
третья программа изменяет ее. В том смысле, что, зная суммы чисел в двух входных 
файлах, мы не можем определить сумму чисел в выходном файле. С разностью чисел в 
файле все лучше: первая программа не меняет разность ((Х+ 1)-(У+ 1)=Х - У), вторая - 
делит ее на 2 (Xl2-У/2=(Х-У)/2), а третья - складывает разности (X-Z=(X-Y)+(Y- Z)). Что 
же не меняется при всех этих преобразованиях - так сразу и не сообразишь. Поставим 
эксперимент (да, математика - наука экспериментальная!).
Исходный файл (5. 19) можно пропустить только через первую программу и получить 
файл (6, 20). Из него можно дальше делать последовательность (7, 21), (8, 22) и Т.д., а 
можно запустить вторую программу и получить файл (3, 1 О). Из него можно сделать 
последовательность (4,11), (5,12) ... (19, 26). Потом можно запустить третью программу на 
(5, 19) и (19, 26) и получить файл (5, 26) ...
Посчитаем разности: 5-19 = -14 = 6-20 = 7-21 = 8-22 = ...; 3-10 = -7 = 4-11 = 5-12 = ... = 19- 
26; 5-26 = -21. Что же общего у чисел -14, -7, -21? Конечно, они все на 7 делятся. Вот пусть 
эта делимость и будет инвариантом.
Действительно, когда разность не меняется, то и делимость сохранится; когда разность 
делится на 2, то делимость на 7 не исчезнет (2 и 7 взаимно просты); а когда разности, 
делящиеся на 7, складываются, то сумма тоже делится на 7. Понятно, что, имея вначале 
файл с разность чисел, делящейся на 7, мы только такие разности и будем получать. Но 
разность 1-2004 = -2003 на 7 не делится, и такой файл мы получить не сможем.