Примени математику (Гашков, Сергеев) - страница 33

10 = 2*5. Как показывает приведенный анализ, рассмотренный способ разрезания на квадраты прямоугольника размером а_>1*а_>2, по существу, является демонстрацией алгоритма Евклида нахождения наибольшего общего делителя пары чисел а_>1 = 135 и а_>2 = 40. Вообще прямоугольник размером а_>1*а_>2 можно разрезать на квадраты со сторонами а_>2, а_>3, а_>4, ..., а_>n+1 в полном согласии с формулами алгоритма Евклида (см. задачу 5.3), причем последовательные частные q_>1, q_>2, ..., q_>n укажут количества соответствующих квадратов.

5.7. Цепочку равенств, получающихся при нахождении наибольшего общего делителя пары чисел а_>1 и а_>2 с помощью алгоритма Евклида (см. задачу 5.3), перепишем следующим образом:

Подставляя в первую строчку вместо дроби ^>а_>2/_>а>3 ее выражение из второй строчки, находим

Подставляя сюда вместо дроби ^>а_>3/_>а>4 ее выражение из третьей строчки, имеем

Производя аналогичные подстановки и далее, из предпоследней строчки получим равенство

в котором останется лишь подставить вместо дроби

ее значение q_>n из последней строчки, после чего выражение будет удовлетворять всем требованиям задачи: все числа q_>2, q_>3, ..., q_>n являются натуральными, так как а_>2>а_>3>...>a_>n-1>a_>n>a_>n+1, а число q_>1 является целым (если a_>1≥a_>2, то натуральным, а если а_>1<а_>2, то нулевым).

5.8.

5.9. Последовательные операции по свертыванию цепной дроби сводятся к операциям двух типов: сложение

и деление . Докажем, что если ^>a/_>b несократимая дробь, то в результате операции любого из указанных двух типов получается также несократимая дробь. Действительно, операция первого типа приводит к дроби , числитель и знаменатель которой не имеют общих делителей, поскольку (см. решение задачи 5.2) справедливы равенства (qb + a, b) = (b, a) = 1. Операция второго типа приводит к дроби ^>b/_>a которая также несократима, ибо (a, b) = (b, а) = 1. Таким образом, раз дробь ^>1/_>q>n несократима, то на каждом шагу, в том числе и на последнем, при свертывании цепной дроби мы получаем несократимую дробь.

Например, для заданной в задаче сократимой дроби имеем

5.10. Для дроби

имеем следующие подходящие дроби:

5.11. Решение этой задачи может показаться на первый взгляд совсем очевидным, поскольку для любой дроби ^>a/_>b можно сначала соединить параллельно b единичных сопротивлений, получив сопротивление, равное ^>1/_>b, а затем размножить эту схему в а экземплярах, соединив их последовательно. При этом в конечном счете нам понадобится а*b единичных сопротивлений. Например, для такого решения п. а) их нужно 7*2 = 14 штук, а для решения п. б) -10*7 = 70 штук. Как показывает приводимое ниже решение, этот очевидный способ далеко не самый экономный: в п. а) достаточно иметь всего 5, а в п. б) - 6 сопротивлений.