Компьютер может производить одну операцию: брать среднее арифметическое двух целых чисел. Даны три числа: m, n и 0, причем m и n не имеют общих делителей и m < n Докажите, что с помощью компьютера из них можно получить
а) единицу;
б) любое целое число от 1 до n.
Заметим, что среднее арифметическое двух целых чисел является целым тогда и только тогда, когда они одной четности (то есть оба четные или оба нечетные). Поскольку компьютер может оперировать лишь с целыми числами, то, без ограничения общности, можно считать, что разрешается брать среднее арифметическое чисел одной четности.
Будем называть множество целых чисел стабильным, если для любых двух его элементов одной четности, их среднее арифметическое также принадлежит этому множеству. Другими словами, если с помощью данного компьютера его нельзя расширить.
Разберемся, как устроены стабильные множества. Будем предполагать, что рассматриваемые множества упорядочены (по возрастанию). Заметим, что четные и нечетные числа в стабильном множестве чередуются. Действительно, если в нем имеются два соседних числа одной четности, то их среднее арифметическое является целым, лежащим между ними, что противоречит определению стабильного множества. Рассмотрим теперь произвольный (не крайний) элемент стабильного множества. Так как он имеет разную четность с обоими своими соседними элементами, то эти два элемента имеют одну четность. Их среднее арифметическое, тем самым, равно рассматриваемому числу. Если любой элемент множества является средним арифметическим соседних, то это — арифметическая прогрессия. (Мы рассматриваем как бесконечные — в одну или обе стороны — прогрессии, так и конечные). Таким образом, любое стабильное множество является арифметической прогрессией.
Итак, мы имеем три числа 0, m и n. По крайней мере два из них имеют одинаковую четность. Мы можем производить операцию взятия среднего арифметического каких-либо двух чисел и добавлять полученное число к имеющимся до тех пор, пока не получим стабильное множество. Поскольку все получаемые числа лежат в интервале от 0 до n, мы получим арифметическую прогрессию с первым членом 0, последним n и содержащим m. Поскольку m и n делятся на разность прогрессии, а по условию они взаимно просты, разность прогрессии равна 1. Значит, мы получим все числа от 0 до n.