Задача
Петя загадал положительную несократимую дробь $x = \frac{m}{n}$. Можно назвать положительную дробь $y$, меньшую 1, и Петя назовёт числитель несократимой дроби, равной сумме $x+y$. Как за два таких действия гарантированно узнать $x$?
Решение
Решение 1:Можно считать, что $m$ и $n$ – натуральные взаимно простые числа. Назовём сначала дробь $\frac12$. Петя вычислит дробь $\frac{2m+n}{2n}$. Общий делитель числителя 2$m+n$ и знаменателя 2$n$ будет также общим делителем чисел 2(2$m+n)−2n = 4m$ и 2$n$ и, поскольку $m$ и $n$ взаимно просты, может равняться 1, 2 или 4. Узнав числитель, который сообщит нам Петя, мы точно будем знать, что 2$m+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)}$.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь