Две задачи о числах Фибоначчи

Квант 1984, №7 с. 14, 16, 17 Тег TLEQ

В случае пешечного эндшпилля, задачу его анализа удается уменшить, проверяя декомпозицию уже не по составу фигур, а по различным положениями пешек. Это можно сделать потому, что пешки не ходят назад и не переходят с одной вертикали на другую без взятый. Декомпозиция оказывается решающим приемом для размещения эндшпилля КЛП—КЛ во внешней памяти ЭВМ.

Недостаток места не позволяет нам расскаазать подробнее о других приемах — использование симметрии, метод «групповой обработки» и др. Эти приемы для возможности удовлетворить ограничения как по объему имеющейся оперативной памяти ЭВМ так и во времени счета, что позволяет довести анализ малофигурных эндшпиллей до конца.

Машина разыгрывает эндшпиль

Как же все это выглядит на практике? Имеются два партнера, делящие ходы почередно, скажем, в эндшпиле КЛП—КЛ. Но в нашем случае один из партнеров — человек, а другой — ЭВМ. В результате процесса ранжирования позиций, проведенного раз и навсегда, в памяти ЭВМ хранится «шпаргалка»—список всех позиций с указанием ранга. Сидя за пультом дисплея, человек набирает позицию и сообщает свой ход. В ответ машина, пользовать «шпаргал-ных от единцы, чисел Фибоначчи никак не является числом Фибоначчи.

Известно, что с возрастанием номеров сами числа Фибоначчи быстро увеличиваются. Так, $f_1=1$ , но $f_{50}=12586269025$ и $f_{100}=354224848179261915075$ . Однако последнюю цифру лю-

кой», находит ранг получившейся позиции и просматривает все ходы из нее, пока не натыкается на оптимальный ход, который и вывесивает на экран дисплея.

Задача 3 (для тех, у кого есть много много времени). В позицини с рисунка 5 больше начинают и выгрывать.

Эта позиция заменяется тем, чтолина оптимального пути от нее до превращения пешки рекордна — 60 ходов! Цепочка ходов из нее мы получили, заставив машину играть за обе стороны.

И что же делать?

Итак, машину научили разыгрывать эндшпиль КЛП—КЛ, причем не только идеально правильно, но и весма быстрого, затрачивая на каждый ход 10—15 секунд (сравните с туририными правилами — 2 часа на 40 ходов).

Аналогично можно научить ЭВМ играть оптимально и в других пятей фигурных эндшпилях. С использованием новых идей, улучшающих алгоритм анализа эндшпиля, а также более мощных машин, видимо, удостраняется доступными для исследований 6—7 фигурные эндшпилии. В то же времяMitтельшпильные шахматные программы, о которых мы уже расскаазвали, даже в многофигурных эндшпилях (10—12 фигур) играют неважно.

Как заполнить эту лакуну, пока не известно. Быть может, удостраться достаточно простого формируемые правила поведения в эндшпиле, рекомендующие пусты и не оптимальные, а близкие к оптимальным ходы. Такие правила можно разрабатывать, исследуя эндшпилли, полный анализ которых уже выполен на ЭВМ. Эти правила оказылись бы весма ценными и для шахматистов, поскольку полезны им удобнее, чем огромными справочными массивами, хранящимися в памяти машины.

Две задачи о числах Фибоначчи

Докажите следующие свойства чисел Фибоначчи (см. с. 17).

Произведение и частное двух любых различных, отличных

ных от единцы, чисел Фибоначчи не являются числами Фибоначчи.

Известно, что с возрастанием номеров сами числа Фибоначчи быстро увеличивается. Так, $f_1=1$ , но $f_{50}=12586269025$ и $f_{100}=354224848179261915075$ . Однако последнюю цифру лю-

Задача 3 (для тех, у кого есть много много времени). В позицини с рисунка 5 больше начинают и выгрывать.

И что же делать?

Итак, машину научили разыгрывать эндшпиль КЛП—КЛ, причем не только идеально правильно, но и весма быстрого, затрачавая на каждый ход 10—15 секунд (сравните с туририными правилами — 2 часа на 40 ходов).

Аналогично можно научить ЭВМ играть оптимально и в других пятей фигурных эндшпилях. С использованием новых идей, улучшющих алгоритм анализа эндшпиля, а также более мощных машин, видимо, удостраняется доступными для исследований 6—7 фигурные эндшпилии. В то же времяMitтельшпильные шахматные программы, о которых мы уже расскаазвали, даже в многофигурных эндшпилях (10—12 фигур) играют неважно.

Как заполнить эту лакуну, пока не известно. Быть может, удостратьсяDEFAULTLY

Ровно через 60 чисел последняя цифра любого числа Фибоначчи перiodически повторяется.

Докажите это.

M. И. Защкин

Львиновое Сerdце (1157—1199). В ряде интальянских городов он завел гаремы, что мало подходило «христанейшем» императору. К преподаванию в основном им Неаполитанском университете, наряду с христанскими учеными, он привлек арабов и евреев. Более того, молва приписьвал ему авторство атеистического памфлета «О трех обманшиках», под которым подразумевались Монсей, Христос и Магомет.

Столь любимые его делом рыцарские туриры, на которых стражошие каLEЧили друг друга на потеху публике, Фридрих II совсем не признавал. Вместо этого он культивировал города мнее кровавые математические современная (нечно среднее между математическими оптимизации и KBH), на которых противники обменывают неударами мечом, а задачими.

На таких турирах и заблистал талант Леонардо Фибоначчи. Этому способствовал хорошее образование, которое дал сыну купец Боначчи, взявший его с собой на Восток и приставивший к нему арабских учительей. Воспследствии Фибоначчи пользовался неизменным покровительством Фридриха II. Это покровительство облегчило дальнейшие торговые поездки Леонардо в сверную Африку, Египет, Сирию, Византию, во время которых он глубоко ознакомился с арабской и греческой науки. (Произведения классков античной науки были известны тогда, главным образом, в арабских переводах.) Покровительство Фридриха II стимулировало также выпуск научных трактатов Фибоначчи: общийшей «Книги абака» (1202 г., переработанный и дополненный варант, 1228 г.), «Практики геометрии» (1220 г.), «Книги квадратов» (1225 г.). По этим книгам, превосходящим по своему уровню арабские и средневековые европейские сочинения, учили математку учть ли не до времени Декарта (XVII в.) и Эйлера (XVIII в.).

Встроении всех книг Леонардо является их произходение от математических туриров. Основную роль в них играют многочисленные решения и комментированные задачи, — иногда те, которые предлагались на турирах самим Леонардо или его основным соперником, выходцем из сцилийского купечества Иоганном Палермским, приворным философом Фридриха II. Заметим еще, что абак — это старинная счетаная докса, нечто вроде русских счетов. Однако «Книги абака» посвящена не практике счета, а теоретической арифметике в широком понимании этого термина. В частности, по этой книге Европые познакомились с арабскими (точнее — индийскими) цифрами и с современной системой записи чисел. Аналогично, «Практика геометрии» посвящена не прикладной (землемерной) геометрии, а теоретической геометрии.

Для характеристки достижения Леонардо достаточно упомянуть две из решенных им задач: найти три числа x, y и z такие, что их сумма, увеличенная как на x², так и на x²+y² и x²+y²+z² была бы полным квадратом (решение Леонардо: x=16/5, y=48/5 и z=144/5) и, особенно, задачу о решении кубического уравнения x³+2x²+10x=20. Леонардо доказывает, что корень этого уравнения не может быть выражен в квадратных радиках (перворе «доказательство невозможности» в европейской математике после античных теореms об irrationalности √2 и других чисел), а затем вычисляет корень уравнения с ошибкой, не превышащей 0,00000000003 (фантастическая точность).

Но из всех достижения Леонардо неблагодарное человекчество помнить сегодня лишь следующую задачу из «Книги абака»:

«Некто помещил пару кроликов в некоем месте, огороженном со всех стороны, чтобы узнать, сколько пар кроликов родится при этом в течение года, если природа кроликов такова, что через месяц пара кроликов произойдет на свет другую пару, аождают кролик со второго месяца после своего рождения».

Ясно, что если считать первую пару кроликов новорожденными (Леонардо не делает этого предположения, что, впрочем, мало отражается на результатах, то на 2-й месяц мы будем по прежнему иметь 1 пару; на 3-й месяц — 1+1=2; на 4-й — 2+1=3 пары (и из двух имеющихся пар потомство даты лишь одна пара); на 5-й — 3+2=5 пар (лишь две родившиеся на 3-й месяц пары даут потомство на 5-м месяц); на 6-й месяц — 5+3=8 пар (ибо потомство даут только те пары, которые родились на 4-м месяц) и т. д. Таким образом, если обозначить число пар

кроликов, имеющих на $n$ -м месте через $f_k$ , то $f_1=1, f_2=1, f_3=2, f_4=3, f_5=5, f_6=8$ и т. д., причем образование этих чисел регулируется общим законом:

$f_n=f_{n-1}+f_{n-2}$ при всех $n>2$ (1)

— ведь число $f_n$ пар кроликов на $n$ -м месте равно числу $f_{n-1}$ пар кроликов на предшествующем месте после числа новых родившихся пар, которое совпадает с числом $f_{n-2}$ пар кроликов, родившихся на $(n-2)$ -м месте (ибо лишь эти пары кроликов дают потомство).

Числа $f_n$ , образующие последовательность 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …, называются новые числа обладают многими удивительными свойствами. Перечислим некоторые из них. Их доказательства читатель может рассматривать как задачи:

$f_1+f_2+\dots+f_n=f_{n+2}-1$ .
а) $f_1+f_3+f_5+\dots+f_{2n-1}=f_{2n}$ ,

$f_2+f_4+f_6+\dots+f_{2n}=f_{2n+1}-1$ .

$f_1^2+f_2^2+\dots+f_n^2=f_nf_{n+1}$ .
а) $f_{2n}=f_{n+1}^2-f_{n-1}^2$ ,

$f_{3n}=f_{n+1}^3+f_n^3-f_{n-1}^3$ .

$f_n^2=f_{n-1}f_{n+1}-(-1)^n$ .
$f_{n+m}=f_{n-1}f_m+f_nf_{m+1}$ .
$f_n$ четно ⇔ делится на 3.
$f_n$ делится на 7 ⇔ делится на 8.
$f_n$ делится на $f_m$ ⇔ $n$ делится на $m$ .

Этот список можно было бы продолжить. Занитересованный читатель найдет много других красивых точекств (свойств чисел $f_n$ ) в популярных книгах, названных в конце статьи, в частиности в заменательных брошюрах и книгах Н. Н. Воробьева. Еще два свойства, присланные в «Квант» М. И. Занкиным, можно посмотреть на с. 14 этого номера.

Рекурентное соотношение (1) позволяет без труда последовательно вычислять числа $f_1, f_2, f_3, \dots$ . Но есть ли явное выражение для общего числа $f_n$ последовательности Фибоначчи, не требущее знания предыдущих членов? Есть, притом совершенное неожиданное. Посудите сами:

$f_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right].$

Подробный разбор доказательства имеется у Воробьева, а также в брошюре А. И. Маркушевича, читрованной в списке литературы; см. также «Квант» 1982, № 1, с. 19.

Особенно возросла популярность чисел Фибоначчи в последовенные годы, что связано с определенными изменениями в самом математике, в частности — с ростом значения комбинаторики и проблем, связанных с целыми числами. Известную роль здесь cfgало неожиданное появление чисел Фибоначчи в некоторых из недавних важных исследований, формировно на каким с этим числам не связаны. В первую очередь мы имеем в виду сенсционное решение молдым ленинградцем Юрием Матиясевичем так называемой десятой проблеми Гильберта*, а также возникновение чисел Фибоначчи в некоторых из душих от американца Ричарда Беллмана направлениях современной прикладной (оптимизционной) математики.

Где только не возникновение числа Фибоначчи! У них есть красивые геометрические применения, важные приложения в биологии растений: например, в размещении на ветке листев тех или иных пород деревьев, в строении чешук ананаса или расположении зерен подсолнуха (явление филотаксиса; см. «Квант», 1979, № 5, с. 53). Задчаа об оптимальной стратегии автоматизации, желающего найти самую выгодную для него скорость машины, то есть такую, при которой она потребляет наменьшее количество бензина на километр проиденного пути, тоже приводит к числом Фибоначчи — вот уже новозможное сразу увидеть, какое отношение эти числа имеют к такой задаче!

Всего не перечислишь. Мы назовем еще лишь разработку оптимальной стратегии в старинной китайской народной игре изяньшизцы, о которой можно прочитать на с. 18 этого номера.

Список литературы

Воробьев Н. Н. Числа Фибоначчи, 1-е издание, М. — Л.: Гостехидат, 1951; 4-е издание, М.: Наука, 1978.
Маркушевич А. И. Возвращные последовательности, М.: Наука, 1979.
Шклярский Д. О., Ченцов Н. Н., Яглом И. И. Избранные задачи и теоремы элементарной математики (аррифметика и алгебра), М.: Наука, 1976.
Дынкин Е. Б., Успенский В. А. Математические беседы, М. — Л.: Гостехидат, 1952.
Стахов А. П. Алгоритмическая теория измешения, М.: Знание, 1979.

См. «Квант», 1971, № 11, с. 31.