Компьютер может производить одну операцию: брать среднее арифметическое двух целых чисел. Даны три числа: m, n и 0, причем m и n не имеют общих делителей и m<n. Докажите, что с помощью компьютера из них можно получить: а) единицу; б) любое целое число от 1 до n.

задан 9 Апр '14 12:44

Числа m, n здесь полагаются натуральными?

(9 Апр '14 12:49) falcao

@falcao: Наверное, да числа натуральные, хотя в условии это не записано, но наверное автор задачи это подразумевал.

(9 Апр '14 12:59) serg55
10|600 символов нужно символов осталось
1

Я буду исходить из предположения, что $%m$% и $%n$% -- натуральные числа (в противном случае, если $%m$% и $%n$% оба отрицательны, единицу получить невозможно).

Рассмотрим множество $%M$% всех целых чисел от $%0$% до $%n$%, которые получить можно (включая сюда те числа, которые были даны изначально). Упорядочим их по возрастанию: $%0=a_0 < a_1 < \ldots < a_k=n$%. Ясно, что в $%M$% имеется по меньшей мере три числа. Рассмотрим произвольную тройку вида $%a_{i-1} < a_i < a_{i+1}$%, где $%1\le i < k$%. Из этих трёх чисел имеются два числа одинаковой чётности, и тогда их среднее арифметическое принадлежит $%M$%. Это не могут быть числа $%a_{i-1}$% и $%a_i$%, так как в противном случае строго между ними оказывается ещё одно число из $%M$%. Аналогично, это не могут быть числа $%a_i$% и $%a_{i+1}$%. Следовательно, речь может идти только о числах $%a_{i-1}$% и $%a_{i+1}$%. Их среднее арифметическое $%\frac{a_{i-1}+a_{i+1}}2$% обязано совпасть с $%a_i$%, так как строго между этими числами нет никаких других чисел из $%M$%. Таким образом, для всех рассматриваемых $%i$% справедливо равенство $%\frac{a_{i-1}+a_{i+1}}2=a_i$%, которое равносильно условию $%a_{i+1}-a_i=a_i-a_{i-1}$%.

Мы пришли к тому, что между соседними элементами множества $%M$% все расстояния одинаковы: $%d=a_1-a_0=a_2-a_1=\cdots=a_k-a_{k-1}$%. Отсюда следует, что все числа из $%M$% кратны $%d$% (ввиду $%a_0=0$%. С учётом того, что $%m$% и $%n$% входят в $%M$%, они оба делятся на $%d$%, откуда $%d=1$%, согласно отсутствию у $%m$% и $%n$% нетривиальных общих делителей. Тем самым, расстояния между соседними числами равны единице, и $%M$% состоит из всех чисел от $%0$% до $%n$% включительно.

ссылка

отвечен 9 Апр '14 13:43

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,929

задан
9 Апр '14 12:44

показан
727 раз

обновлен
9 Апр '14 13:43

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru