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