|
|
 |
Условие
Петя загадал положительную несократимую дробь $x = {m}{n}$. За один ход Вася называет положительную несократимую дробь $y$, не превосходящую 1, и Петя в ответ сообщает Васе числитель несократимой дроби, равной сумме $x+y$. Как Васе за два хода гарантированно узнать $x$?Решение 1
Как известно, для целых чисел $a$, $b$ и $k$ выполнено равенство $$\text{НОД}(a + kb, b) = \text{НОД}(a, b).$$ Пусть первым ходом Вася назовёт дробь $y =\frac{1}{1}$. Петя вычислит дробь $x + y = \frac{m + n}{n}$. Поскольку числа $m$ и $n$ взаимно просты, то $$\text{НОД}(m + n, n) = \text{НОД}(m, n) = 1,$$ то есть дробь несократима, и Петя сообщит число $a = m + n$.Пусть вторым ходом Вася назовёт дробь $y = \frac{1}{a}$. Петя вычислит дробь $x + y = \frac{am + n}{an}$. Эта дробь несократима, поскольку $$\text{НОД}(am + n, a) = \text{НОД}(n, a) = \text{НОД}(n, m+n) = 1$$ и аналогично $\text{НОД}(am + n, n) = 1$. Следовательно, Петя сообщит число $b = am + n$.
Поделив $b$ на $a$ с остатком, Вася узнает $n$. Вычислив разность $a-n$, Вася узнает $m$. Таким образом, Вася сможет узнать загаданную дробь.
Решение 2
Пусть, как и в первом решение, Вася первым ходом назовёт дробь $y = \frac{1}{1}$ и получит в ответ от Пети число $a = m + n$.Пусть вторым ходом Вася назовёт дробь $y = \frac{1}{(a!)^2}$. Петя вычислит дробь $$x + y = \frac{m \cdot \dfrac{(a!)^2}{n} + 1}{(a!)^2} = \frac{m \cdot {a!} \cdot \dfrac{a!}{n} + 1}{(a!)^2}. $$ Допустим, дробь можно сократить на какое-то простое число $p$. Тогда $p$ – это делитель числа $a!$. Но $m \cdot a! \cdot \frac{a!}{n}$ делится на $p$, поэтому весь числитель на $p$ не делится, противоречие. Следовательно, Петя сообщит Васе число $b = m \cdot \frac{(a!)^2}{n} + 1$.
Вычислив неполное частное при делении $b$ на $a!$, Вася узнает число $m \cdot \frac{a!}{n}$. Поделив это число на $a!$, Вася узнает $\frac{m}{n}$, то есть загаданную дробь.
