Задача 67428
|
|
 |
Условие
Петя загадал положительную несократимую дробь $x = \frac{m}{n}$. Можно назвать положительную дробь $y$, меньшую $1$, и Петя назовёт числитель несократимой дроби, равной сумме $x+y$. Как за два таких действия гарантированно узнать $x$?Решение 1
Можно считать, что $m$ и $n$ — натуральные взаимно простые числа. Назовём сначала дробь $\frac12$. Петя вычислит дробь $\frac{2m+n}{2n}$. Общий делитель числителя $2m+n$ и знаменателя $2n$ будет также общим делителем чисел $2(2m+n)−2n = 4m$ и $2n$ и, поскольку $m$ и $n$ взаимно просты, может равняться $1$, $2$ или $4$. Узнав числитель, который сообщит нам Петя, мы точно будем знать, что $2m+n$ не больше этого числителя, умноженного на $4$. Следующим ходом назовём дробь $\frac{1}{p}$, где $p$ — простое число, большее учетверённого числителя, — тогда $p$ будет больше и $m$, и $n$. Петя вычислит дробь $\frac{p \cdot m+n}{p\cdot n}$, она будет несократимой. Узнав её числитель $p\cdot m+n$, возьмём от него остаток от деления на $p$ и таким образом найдём $n$. Вычтя из числителя $n$ и поделив на $p$, найдём $m$.Решение 2
Назовём сначала $\frac13$ и получим ответ $a$, а потом $\frac23$ и получим ответ $b$. Возможны четыре случая.Случай 1: $n$ не кратно $3$. Тогда $a = 3m+n$, $b = 3m+2n$. Заметим, что $a < b < 2a$. Пусть $n = 3k$. Тогда $m$ не кратно $3$.
Случай 2: $k$ кратно $3$. Тогда $a = m+k$, $b = m+2k$. Здесь тоже $a < b < 2a$.
Случай 3: $k \equiv m\,(\mathrm{mod}\,3)$. Тогда $a = m+k$, $b = \frac{m+2k}{3}$. Здесь $b < a < 3b$.
Случай 4: $k \equiv 2m\,(\mathrm{mod}\,3)$. Тогда $a = \frac{m+k}{3}$, $b=m+2k$. Здесь $b>3a$. В случаях $1$ и $2$, как легко проверить, $\frac{m}{n} = \frac{2a−b}{3(b −a)}$. Случаи 3 и 4 отличаются от них и между собой по указанным соотношениям между $a$ и $b$. В случае 3 получаем $\frac{m}{n} = \frac{2a−3b}{3(3b −a)}$, в случае 4 получаем $\frac{m}{n} = \frac{6a−b}{3(b −3a)}$.
