Условие
С ненулевым числом разрешается проделывать следующие
операции: 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 |
Выбрана 1 задача 
