Версия для печати
Убрать все задачи

---

Петя загадал положительную несократимую дробь $x = \frac{m}{n}$. За один ход Вася называет положительную несократимую дробь $y$, не превосходящую 1, и Петя в ответ сообщает Васе числитель несократимой дроби, равной сумме $x+y$. Как Васе за два хода гарантированно узнать $x$?

   Решение

Темы:    [ Обыкновенные дроби ] [ НОД и НОК. Взаимная простота ] [ Теория алгоритмов (прочее) ]

Сложность: 3+ Классы: 6,7,8,9,10,11

Прислать комментарий

Условие

Петя загадал положительную несократимую дробь $x = \frac{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}$, то есть загаданную дробь.

Замечания

Существует множество других примеров дробей, которые может назвать Вася. Например, дроби $\frac{1}{1}$ и $\frac{1}{2}$.
См. также задачу 67428.

Источники и прецеденты использования