Но это будет итоговая "светлая цель", к которой мы дойдём, а пока давайте начнём с совсем простого: посчитаем буквы. (Почему? Да просто потому, что если вдруг есть непонятный объект, так давайте его измерим, насколько получится, вдруг что интересное найдём.)
Математические байки
Вот первые несколько образов: w_1=А w_2=АБ w_3=АБА w_4=АБААБ w_5=АБААБАБА Явно видно, что следующее слово продолжает предыдущее — что мгновенно доказывается по индукции. Значит, есть одно бесконечное слово, у которого все эти слова являются началами. Это…
Сколько букв в словах w_1, w_2, w_3,...? Посчитав, видимо знакомую нам последовательность
1, 2, 3, 5, 8, ...
А сколько по отдельности букв А и Б?
1, 2, 3, 5, 8, ...
А сколько по отдельности букв А и Б?
Сразу видны числа Фибоначчи; а как бы это доказать?
Мы знаем, что следующее слово продолжает предыдущее, не получится ли что-то увидеть из этого?
Давайте посмотрим, что остаётся, если из нового слова убрать идущее перед ним:
Мы знаем, что следующее слово продолжает предыдущее, не получится ли что-то увидеть из этого?
Давайте посмотрим, что остаётся, если из нового слова убрать идущее перед ним:
Невооружённым глазом видно, что остаётся то слово, что было до того. То есть
w_{n+1} = w_n w_{n-1}.
И когда это написано, доказательство тоже мгновенно проводится по индукции, из базы либо АБА= АБ А,
либо даже АБ= А Б с формальным добавлением w_0=Б.
w_{n+1} = w_n w_{n-1}.
И когда это написано, доказательство тоже мгновенно проводится по индукции, из базы либо АБА= АБ А,
либо даже АБ= А Б с формальным добавлением w_0=Б.
Математические байки
Невооружённым глазом видно, что остаётся то слово, что было до того. То есть w_{n+1} = w_n w_{n-1}. И когда это написано, доказательство тоже мгновенно проводится по индукции, из базы либо АБА= АБ А, либо даже АБ= А Б с формальным добавлением w_0=Б.
Теперь понятно, почему бесконечное слово называют "словом Фибоначчи": последовательность слов, которая к нему приводит, получается как раз из Фибоначчи-подобного соотношения.
Но давайте продолжим нашу деятельность по счёту букв. А именно, давайте посмотрим, сколько букв А и Б оказывается среди первых k букв слова Фибоначчи — и отметим соответствующую точку на плоскости (по оси абсцисс отложив буквы А, а по оси ординат буквы Б). Получится этакая "змейка": при добавлении одной буквы мы сдвинемся на расстояние 1.
Но давайте продолжим нашу деятельность по счёту букв. А именно, давайте посмотрим, сколько букв А и Б оказывается среди первых k букв слова Фибоначчи — и отметим соответствующую точку на плоскости (по оси абсцисс отложив буквы А, а по оси ординат буквы Б). Получится этакая "змейка": при добавлении одной буквы мы сдвинемся на расстояние 1.
Сразу кажется, что она очень хорошо "выдерживает направление". Кстати, коэффициент наклона того направления, в котором она идёт (если предположить, что он есть) — золотое сечение, точнее, обратная к нему величина 1/Ф (букв А больше, а традиционно Ф^2=Ф+1).
Потому что отношение последовательных чисел Фибоначчи стремится к золотому сечению, а мы знаем, что в подслове w_n количество букв А и Б это последовательные числа Фибоначчи.
Потому что отношение последовательных чисел Фибоначчи стремится к золотому сечению, а мы знаем, что в подслове w_n количество букв А и Б это последовательные числа Фибоначчи.
Но буквально так мы что-то говорим только про слова w_n — а они становятся всё длиннее и длиннее, и формально мы пока ничего не сказали про подслова длиной между |w_n| и |w_{n+1}|.
И всё равно; давайте посмотрим, насколько хорошо точки ложатся на какую-то прямую — попробовав заключить их в полосу. Оказывается, что это полоса вполне небольшого размера:
А прямые, которые её ограничивают — проходят через точки (-1,0) и (0,-1); и вся эта змейка, какой бы длины она не была, не выходит за рамки этой весьма неширокой полосы.
Если последняя посчитанная буква А — поставим красную точку, если Б — синюю. Вот, что получится:
Очень естественно, что красные точки в целом ниже/правее синих. Но что будет, если мы их спроецируем на перпендикулярный отрезок?
Окажется, что проекции красных точек заметают один отрезок, проекции синих другой, и эти отрезки не пересекаются.