МОШ 2024, 9 класс, задача 3
Петя загадал положительную несократимую дробь . За один ход Вася называет положительную несократимую дробь , не превосходящую , и Петя в ответ сообщает Васе числитель несократимой дроби, равной сумме . Как Васе за два хода гарантированно узнать ?
(М. Дидин)
Ответ
Решение 1. Как известно, для целых чисел , и выполнено равенство
Пусть первым ходом Вася назовёт дробь . Петя вычислит дробь . Поскольку числа и взаимно просты, то
то есть дробь несократима, и Петя сообщит число .
Пусть вторым ходом Вася назовёт дробь . Петя вычислит дробь . Эта дробь несократима, поскольку
и аналогично . Следовательно, Петя сообщит число . Поделив на с остатком, Вася узнает . Вычислив разность , Вася узнает . Таким образом, Вася сможет узнать загаданную дробь.
Решение 2. Как и в первом решении, пусть Вася первым ходом назовёт дробь и получит в ответ от Пети число .
Пусть вторым ходом Вася назовёт дробь . Петя вычислит дробь
Допустим, дробь можно сократить на какое-то простое число . Тогда — это делитель числа . Но делится на , поэтому весь числитель на не делится, противоречие.
Следовательно, Петя сообщит Васе число .
Вычислив неполное частное при делении на , Вася узнает число . Поделив это число на , Вася узнает , то есть загаданную дробь.
Замечание. Существует множество других примеров дробей, которые может назвать Вася. Например, дроби и .