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