|
|
 |
Условие
На доске написано натуральное число. Если на доске написано число x, то можно дописать на нее число 2x + 1 или x/x+2. В какой-то момент выяснилось, что на доске присутствует число 2008. Докажите, что оно там было с самого начала.
Решение
Можно считать, что "лишних" чисел на доску не выписывалось, то есть все числа "участвовали" в получении числа 2008. Заметим, что все выписанные числа положительны. Пусть в некоторый момент на доске написано рациональное число, в несократимой записи имеющее вид
x = p/q. Тогда можно дописать число 2x + 1 = 2p+q/q или x/x+2 = p/p+2q. Заметим, что если какая-нибудь из этих дробей сократима, то только на 2. Действительно, НОД(2p + q, q) = НОД(2p, q) ≤ 2НОД(p, q) = 2 и аналогично НОД(p, p+2q) ≤ 2. Поэтому сумма числителя и знаменателя в несократимой записи нового числа равна либо (2p + q) + q = p + (p + 2q) = 2(p + q), либо ½·2(p + q) = p + q. Таким образом, сумма числителя и знаменателя в несократимой записи либо не изменяется, либо удваивается. Так как в конце она оказалась равной 2008 + 1 = 2009, то удваиваться она не могла, и изначально она тоже была равна 2009. Так как исходное число было натуральным, то его знаменатель был равен 1, а числитель, соответственно, 2009 – 1 = 2008.
