Последовательность Фибоначчи и число Фидия.

Последовательность Фибоначчи Fn  определяется так:  F0=1 F1=1  Fi=F(i-1) + F(i-2)
Заведем новую последовательность Qn и определим её так:  Qi=F(i+1)/Fi
Докажем, что Qn сходится к числу Фидия (золотому сечению) при n стремится к бесконечности.
Начнем издалека. Чтобы доказать этот факт, докажем одно общеизвестное утверждение про числа Фибоначчи.

Лемма. Fn^2-F(n-1)F(n+1)=(-1)^n.
Доказательство.
Доказывать будем по индукции.
База. При n=1 верно.
Предположение. Предположим верно при n=k. Fk^2-F(k-1)F(k+1)=(-1)^k
Переход. Распишем для n=k+1.
F(k+1)^2-Fk*F(k+2)=(-1)^(k+1) <=>
F(k+1)^2-Fk^2-Fk*F(k+1)=(-1)^(k+1) <=>
F(k-1)F(k+1)-Fk^2=(-1)^(k+1)
Сложим с предположением:
0=(-1)^k+(-1)^(k+1), что, очевидно, справедливо.
Лемма доказана.

Рассмотрим теперь разность двух соседних элементов Qn^(-1).
bQn^(-1)=Fi/F(i+1)-F(i+1)/F(i+2)=-(F(i+1)^2-Fi*F(i+2))/(F(i+1)*F(i+2))
Заметим, что по нашей лемме, числитель дроби всегда будет по модулю равен 1, а знаменатель будет неограниченно возрастать. Таким образом, по критерию сходимости Коши числовой последовательности, наша последовательность имеет предел.

Попытаемся найти этот предел. Заметим, что последовательность, обратную к нашей, можно описать рекуррентной формулой:
Qn^(-1)=1/(1+Q(n-1)^(-1)) Тогда верно,
x=1/(1+x), где x>0 - предел Qn^(-1)
Решая квадратное уравнение, находим, что единственным числом, которое нам подходит является (sqrt(5)-1)/2.
Таким образом, последовательность, обратная к нашей сходится к (sqrt(5)-1)/2. Из арифметики пределов следует, что наша последовательность сходится к 1/((sqrt(5)-1)/2)=(1+sqrt(5))/2.
А это и есть золотое сечение или число Фидия.

Немного о графах. Теорема о графе пересечения многоугольников.

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

Теорема 3. Граф пересечения двух многоугольников,образованный вершинами многоугольников, их точками пересечения и отрезками, которые их соединяют, является эйлеровым, если количество точек их пересечения не более, чем конечно.

Доказательство.
Если два многоугольник пересекаются, значит пересекаются какие-то их ребра.
Здесь возможны несколько случаев.

Пример для пункта 1.

1) Пересечение двух отрезков образует отрезок. Как известно, на отрезке точек вовсе не конечное число, поэтому, согласно формулировке теоремы, такие многоугольники мы рассматривать не будем. Как видно из рисунка слева, они не всегда являются эйлеровыми графами.


2) Пересечение двух отрезков не образует отрезок. Тогда два отрезка могут пересекаться в какой-то точке. Если точка пересечения не является вершиной никакого из многоугольников, тогда все очевидно, в образованном графе она имеет степень 4. Если же она является вершиной только одного многоугольника, то и здесь, очевидно, полученная точка будет иметь степень 4 (т.к. в графе любого многоугольника степени всех вершин равны 2). Иначе, если она является вершиной обоих многоугольников, то степени просто суммируются, то есть степень полученной вершины равна 4.

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

Обобщим нашу теорему на большое количество многоугольников.
Теорема 4. Граф пересечения любого количества многоугольников,образованный вершинами многоугольников, их точками пересечения и отрезками, которые их соединяют, является эйлеровым, если для графа пересечения любых двух многоугольников из рассматриваемого набора можно утверждать, что они имеют не более, чем конечное число точек пересечения.

Доказательство.
Доказывать будем по индукции.
База. См. Теорема 3.
Предположение. Предположим для количества многоугольников K теорема верна.
Переход. Докажем, что для количества многоугольников K+1 теорема также верна.
Действительно, если граф при K многоугольниках эйлеровый, значит, степени его вершин четные числа. Понятно (см. опять же теорему 3), что при пересечении полученной конструкции с еще одним многоугольником подходящим нам образом, могут либо появляться новые вершины со степенью 4, либо степени старых вершин будут увеличиваться на 2. Таким образом, четность не изменится. Откуда следует, что граф будет эйлеровым и при K+1.
Теорема доказана.

Интересности. Теорема о разбиении на квадраты.

Теорема. Любое натуральное число можно представить в виде суммы сколь угодно большого количества квадратов различных рациональных чисел.
Доказательство.
Действительно, возьмем наше натуральное число N и представим его в виде суммы N единиц.
N=1+1+...+1 (N раз)
Тогда доказательство нашего утверждения сводится к доказательству двух лемм.

Лемма 1. Единицу можно представить в виде суммы сколь угодно большого количества квадратов различных рациональных чисел.

Доказательство.

Действительно, 1 = ((4/5)^2+(3/5)^2) = (((4/5)^2)*1+((3/5)^2)*1) =

= (((4/5)^2)*((4/5)^2+(3/5)^2)+(3/5)^2))

Повторим подобное столько, сколько нам нужно, раз, откроем скобки и получим сколь угодно большое количество квадратов рациональных чисел.

 Немного не отсюда, но все же.

Лемма 2. Единицу можно представить в виде суммы квадратов двух рациональных чисел бесконечным количеством способов.
Доказательство.
Действительно, (a/c)^2+(b/c)^2=1 равносильно a^2+b^2=c^2, где НОД(a, b, c)=1.
Таким образом, эта лемма сводится к доказательству бесконечности количества примитивных пифагоровых троек, что очевидно:
Любая примитивная пифагорова тройка задается произвольными числами m и n разной четности в виде кортежа (m^2-n^2, 2*m*n, m^2+n^2). Таким образом, их бесконечно много.

Немного о графах. Эйлеровы графы.

В городе Кёнигсберг (ныне Калининград) бытовала загадка: как пройти по всем семи мостам города, так, чтобы побывать на каждом мосту ровно один раз. В 1736 году эту загадку решил Леонард Эйлер, представив широкой общественности критерий существования в графе эйлерова (теперь его так называют) цикла.

Упрощенная схема мостов Кенигсберга.

 Определение 7. Эйлеров путь в графе - такой путь, который проходит через все ребра ровно по одному разу.

Определение 8. Цикл в графе - это такой конечный путь, в котором начальная и конечная вершины совпадают.

Определение 9. Эйлеров цикл - это эйлеров путь, являющийся при этом циклом. Граф, в котором есть такой цикл, называют эйлеровым.


Теорема 2. Связный граф является эйлеровым тогда и только тогда, когда все степени его вершин - четные числа.

Доказательство.  В действительности, если эйлеров цикл входит в вершину по одному ребру, то он должен выйти из нее по другому. Таким образом условие четности очевидно. Покажем теперь, что в связном графе с четными степенями вершин такой цикл существует.
Начнем путь P в произвольной вершине a графа G и будем продолжать его по все новым и новым ребрам. Так как все степени четные, этот процесс закончится в a. Если полученный цикл P не является эйлеровым, удалим из графа G все ребра, через которые проходит P. Понятно, что в оставшемся подграфе все степени останутся четными и найдется хотя бы одна вершина b, инцидентная какому-либо ребру из P. Тогда мы можем построить из нее подобный P цикл P' и проделать для нее вновь все те же самые операции.
Переобозначим: P=P(a, b) + P' + P(b, a), где P(k, l) - часть цикла P, соединяющая k и l.
Легко видеть, что рано или поздно ребра в графе кончатся и тогда цикл P станет эйлеровым.

Немного о графах. Основные понятия и смежные задачи.

Определение 1. Назовем V множеством вершин графа. Тогда граф G=G(V) с множеством вершин V есть некоторое семейство сочетаний вида E=(a, b), где a и b принадлежат V, указывающее какие вершины считаются соединенными. Каждая такая пара называется ребром графа. Элементы a и b  называются вершинами графа. Если в семействе найдется такое E'=(k, l), то вершины k и l называют инцидентными ребру E'.

Задача 1. Можно ли из 37 ниток сплести сетку так, чтобы каждая нитка была связана ровно с пятью другими? (Московская математическая регата, 10 класс, 97/98 учебный год, второй тур, задача 3)

Определение 2. (подсказка) Локальной степенью вершины a графа G, называют количество таких ребер E' графа G, что a инцидентно E'.

Решение:
Первый вариант. Предположим, можно. Построим граф с 37 вершинами, каждая из которых характеризует какую-либо нитку. Так как каждая нитка должна быть соединена ровно с 5 другими, то количество ребер в таком графе (37*5)/2 (делим на два, потому что каждое ребро мы считаем для обеих инцидентных вершин). Таким образом, количество ребер графа - нецелое число. Коллапс. Значит, наше предположение неверно, значит, верно обратное. Вся задача.

Определение 3. Граф называется конечным, если число его ребер конечно, и бесконечным - в противном случае.

Чтобы привести второй вариант решения, докажем небольшую теорему.

Теорема 1. В любом конечном графе количество вершин с нечетной локальной степенью четно.
Доказательство. Обозначим количество ребер графа за v.
Понятно, что v равно сумма локальных степеней всех вершин пополам. Отсюда следует, что сумма локальных степеней - четное число. Тогда, если мы удалим из графа все вершины с четными локальными степенями, сумма локальных степеней все равно останется четной. Следовательно количество вершин с нечетными локальными степенями четно.

Второй вариант. Предположим, можно. Если получившуюся сеть представить, как граф, то количество вершин такого графа - 37(нечетное число), а степень каждой вершины - 5(нечетное число). Противоречие с теоремой 1. Значит, наше предположение неверно, значит, верно обратное. Вся задача.

Задача 2. Куб со стороной n (n не меньше трех) разбит перегородками на единичные кубики. Какое минимальное число перегородок нужно удалить, чтобы из каждого кубика можно было добраться до границы куба?(Региональный этап всероссийской олимпиады школьников по математике, 10 класс, 97/98 учебный год, второй день, задача 3)

Определение 4. Путь  - это такая конечная или бесконечная последовательность ребер, что начало каждого следующего ребра, является концом предыдущего.

Определение 5. Граф называется связным тогда и только тогда, когда из каждой вершины графа существует путь в любую другую.

Определение 6 .Вообще говоря, ясно, что любой граф G можно разбить на подграфы, каждый из которых связен, причем ни из какой вершины любого подграфа невозможно построить путь в любую вершину любого другого подграфа. Такие подграфы называются компонентами связности графа G. (в единственном числе - компонента связности)

Упражнение. Докажите, что каждый граф можно представить в виде совокупности его связных компонент единственным образом.

Решение:
Удалим из куба его внешний слой "толщины" 1, вместе со всеми его перегородками. У нас останется куб со стороной (n - 2), в нем (n - 2)^3 единичных кубиков. Рассмотрим граф, в котором каждый кубик является вершиной. Причем изначально ни одна из вершин не соединена ни с какой другой. Переформулируем вопрос задачи. Узнать, какое минимальное количество ребер нужно провести в таком графе, чтобы он стал связным. Ответом будет являться это количество, увеличенное на единицу (нужно открыть хотя бы одну внешнюю перегородку). Итак, найдем это число. Изначально компонент связности столько же, сколько вершин в графе, то есть (n - 2)^3. Заметим, что каждое проведенное ребро уменьшает количество компонент связности либо на ноль, либо на единицу. А нам нужно, чтобы их осталось ровно одна. Тогда понятно, что минимальное число ребер, которое нужно провести это (n - 2)^3 - 1. Поясним, как провести так ребра. Изначально пометим любую вершину. На каждом следующем шаге будем выбирать любую вершину из уже помеченных и соединять ее с любой другой из еще не помеченных. Каждый такой шаг будет соответствовать какому-то ребру, а так как шагов будет ровно (n - 2)^3 - 1, то ребер будет столько же. То есть ответ (n - 2)^3 - 1 + 1 = (n - 2)^3