ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109493
Темы:    [ Рациональные и иррациональные числа ]
[ Процессы и операции ]
[ Итерации ]
[ Индукция (прочее) ]
[ Теория алгоритмов (прочее) ]
Сложность: 4+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

С ненулевым числом разрешается проделывать следующие операции: x , x . Верно ли, что из каждого ненулевого рационального числа можно получить каждое рациональное число с помощью конечного числа таких операций?

Решение

Обозначим наши операции через f(x)= , g(x)= . Докажем сначала, что, последовательно применяя их, мы можем получить операции, обратные к f и g . Имеем f(g(f(x)))=-x и f(g(f(g(f(x)))))= при x -1 . Поэтому f(g(f(f(g(f(x))))))=x при x -1 и f(g(f(g(f(g(x))))))=x при x 1 . Далее, из 2 можно получить -2 (и наоборот). Кроме того, f(-2)= , g()=1 . Значит, можно получить 1 из 2. Так как g(-1)=-2 , а из -2 можно получить 2, можно получить 2 из -1 . Так как g(2)=- и f(-)=-1 , можно получить -1 из -2 . Итак, обратимость доказана. Значит, достаточно доказать, что из единицы можно получить все положительные рациональные числа. Докажем это индукцией по сумме числителя и знаменателя несократимой дроби, представляющей наше рациональное число . База индукции для m+n=2 очевидна. Допустим, что при m+n<k число можно получить из единицы. Докажем, что тогда и при m+n=k число получается из единицы. Если

m>n, то =1+ и n+(m-n)=m<m+n,

поэтому число можно получить по предположению индукции. Если же
m<n, то = и (n-m)+m=n<m+n,

поэтому число можно получить по предположению индукции. Значит, в обоих случаях число можно получить из единицы, индукционный переход доказан.

Ответ

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 70
Год 2007
вариант
Класс 10
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .