Из правильной несократимой дроби ba, где a и b — натуральные числа, за один ход получают дробь 2a+ba+b.
а) Можно ли за несколько таких ходов из дроби 32 получить дробь 4129?
б) Можно ли за два таких хода из некоторой дроби получить дробь 76?
в) Несократимая дробь dc больше 0,7. Найдите наименьшую дробь dc, которую нельзя получить ни из какой правильной несократимой дроби за два таких хода.
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Положим x=ba. Исходная правильная дробь соответствует 0<x<1. Один ход задаётся дробно-линейной функцией. Определитель матрицы операции равен −1, поэтому взаимная простота числителя и знаменателя сохраняется: дополнительное сокращение не скрывает ходов.
p=1
q=2
y=2x+1x+1
Шаг 2. На каждом ходе знаменатель строго увеличивается. Поэтому до заданного знаменателя можно выполнить лишь конечное число ходов. Последовательно применяем одну и ту же формулу; таблица содержит все состояния до достижения или превышения нужного знаменателя.
T=((2;3);(5;7);(12;17);(29;41))
Шаг 3. Да. Необходимые условия выполнены и приведённая последовательность ходов достигает цели.
Шаг 1. Положим x=ba. Исходная правильная дробь соответствует 0<x<1. Один ход задаётся дробно-линейной функцией. Определитель матрицы операции равен −1, поэтому взаимная простота числителя и знаменателя сохраняется: дополнительное сокращение не скрывает ходов.
Шаг 2. Для двух ходов перемножаем матрицу операции саму на себя. Её определитель равен 1, поэтому обратная матрица целочисленна. Применяем её к заданной несократимой дроби. Результат подходит тогда и только тогда, когда оба числа натуральны и числитель меньше знаменателя.
T=((3;2);(4;3))
A=4
B=−3
Шаг 3. Нет. Сохранённые ограничения или полный конечный список обратных кандидатов исключают цель.
Шаг 1. Двукратное дробно-линейное преобразование строго возрастает на 0<x<1. Его значения составляют открытый промежуток между значениями при 0 и 1. Всякая рациональная дробь внутри него имеет правильный рациональный прообраз; обе границы недостижимы. Сравниваем заданную границу с этим промежутком и выбираем ближайший недостижимый конец.