|
|
 |
Условие
Компьютер может производить одну операцию: брать среднее арифметическое двух целых чисел. Даны три числа: m, n и 0, причём m и n не имеют общих делителей и m < n. Докажите, что с помощью компьютера из них можно получить
а) единицу;
б) любое целое число от 1 до n.
Решение
Заметим, что среднее арифметическое двух целых чисел является целым тогда и только тогда, когда они одной чётности (то есть оба чётные или оба нечётные). Поскольку компьютер может оперировать лишь с целыми числами, то можно считать, что разрешается брать среднее арифметическое чисел одной чётности.
Будем называть множество целых чисел стабильным, если для каждых двух его элементов одной чётности, их среднее арифметическое также принадлежит этому множеству (другими словами, если с помощью данного компьютера его нельзя расширить).
Упорядочим стабильное множество по возрастанию. Тогда чётные и нечётные числа в нём чередуются. Действительно, если в нём имеются два соседних числа
одной чётности, то их среднее арифметическое является целым, лежащим между ними, что противоречит определению стабильного множества.
Рассмотрим произвольный (не крайний) элемент этого множества. Так как он имеет разную чётность с обоими своими соседями, то эти два элемента имеют одну чётность. Их среднее арифметическое, тем самым, равно рассматриваемому числу. Так как каждый элемент множества является средним арифметическим соседних, то это – арифметическая прогрессия. (Мы рассматриваем как бесконечные – в одну или обе стороны – прогрессии, так и конечные.)
Мы имеем три числа 0, m и n. По крайней мере два из них имеют одинаковую чётность. Будем производить операцию взятия среднего арифметического каких-либо двух чисел и добавлять полученное число к имеющимся до тех пор, пока не получим стабильное множество. Поскольку все получаемые числа лежат в интервале от 0 до n, мы, как показано выше, получим арифметическую прогрессию с первым членом 0, последним n и содержащую m. Поскольку m и n делятся на разность прогрессии, а по условию они взаимно просты, разность прогрессии равна 1. Значит, мы получим все числа от 0 до n.
Замечания
Источник решения: книга В.О. Бугаенко "Турниры им. Ломоносова. Конкурсы по математике". МЦНМО-ЧеРо. 1998.
