?

Log in

No account? Create an account

Entries by category: наука

Теорема Ферма на youtube
r_aa
На http://youtube.com тоже есть записи с "доказательствами" теоремы Ферма. Вот пример одной из них:



Автор попутешествовал по пустыне и решил выложить "доказательство". Метод прост: запутаться в обозначениях и прийти к противоречию. Я даже ошибки указывать не буду, это подойдет в качестве упражнения для школьников. Кстати, все видео смотреть не надо, так как "доказательство" занимает одну страницу, достаточно сразу поставить на паузу и просмотреть.

Для полноты картины ссылка на страничку автора http://alpo-02.livejournal.com/. Там все атрибуты ферматиков: сенсационность, разные предисловия и послесловия, философствования и прочие рюшечки. А также числовые примеры, куда ж без них.

Числа Рамсея
r_aa
Так уж случилось, что самым интересным для меня разделом математики является теория графов. А касательно теории графов - числа Рамсея. Существует общее формальное определение чисел Рамсея, но приводить его я не вижу смысла, так как эти числа настолько сложны для вычисления, что даже для самого простого случая найдено их не так много. Итак, определим число Рамсея в простейшем случае:

Число Рамсея R(k, m) это наименьшее число n такое, что в любом графе с n вершинами, найдутся либо k попарно смежных, либо m попарно несмежных.

Теорема Рамсея гарантирует существование чисел Рамсея для любых k и m. Таким образом можно говорить о содержании в бесконечном графе высокоорганизованной структуры любой сложности. Но об этом позже (быть может). А пока хочется остановиться на числах Рамсея. Для удобства перефразируем определение:

Число Рамсея R(k, m) это наименьшее число n такое, что в любом полном графе с n вершинами, ребра которого раскрашены в красный и синий цвета, найдется либо подграф с k вершинами, все ребра которого окрашены в красный цвет, либо подграф с m вершинами, все ребра которого окрашены в синий цвет.

Чтобы понять сложность вычисления чисел Рамсея, то следует отметить что число R(5, 5) до сих пор не найдено.

Можно заметить три очевидных факта, касающихся чисел Рамсея:

1. R(k, m) = R(m, k)
2. R(1, m) = 1
3. R(2, m) = m

Остальные числа вычисляются индивидуально.

Задача о вычислении R(3, 3) известна как "задача о вечеринке": среди любых 6 человек найдется либо 3 попарно знакомых, либо 3 попарно незнакомых. Другими словами R(3, 3) <= 6. Доказательство строится следующим образом (в терминах второго приведенного определения):

Изобразим граф с шестью вершинами и возьмем одну из них - A:

Вершина A соединена с пятью другими вершинами (красными и синими ребрами). Без ограничения общности можно считать, что она соединена красными ребрами по крайней мере с тремя вершинами - B, C, D. Далее, если одно из ребер BC, CD, BD красное (например BC), то имеем красный треугольник (ABC). Если же все они синие, то BCD - синий треугольник. Конец доказательства.

Имея в виду то, что число 5 не удовлетворяет требованиям задачи, получаем R(3, 3) = 6.

Дальше докажем, что R(3, 4) = 9. Сначала установим, что R(3, 4) > 8. Для этого достаточно привести пример раскраски графа из 8 вершин, не содержащего красных треугольников и полных синих подграфов из 4 вершин:



Осталось доказать, что полный граф из 9 вершин так раскрасить нельзя. Допустим, такая раскраска возможна. Будем рассуждать как в предыдущем доказательстве. Возьмем одну из вершин (A), с остальными вершинами она соединена 8 ребрами. Пусть k из них покрашены в красный цвет, а остальные 8-k - в синий.
Если k >= R(2, 4) = 4, то A соединена красными ребрами хотя бы с четырьмя вершинами (B, C, D, E). Если две из этих вершин соединены красным ребром, то сразу имеем красный треугольник, а если нет, то BCDE - полный синий граф из четырех вершин. Значит k < 4.
Аналогичным образом 8-k < R(3, 3) = 6.
Из этих двух неравенств имеем (k < 4) && (k > 2) => k = 3.
Так как наши рассуждения не зависят от выбора вершины, то можно утверждать, что из любой вершины выходит ровно три красных ребра, а значит общее число красных ребер в графе равно 3 * 9 / 2. Но это число не является целым, мы пришли к противоречию. Следовательно требуемой раскраски не существует и R(3, 4) = 9. Конец доказательства.

P.S. Данное доказательство пока не слишком сложное, но все же сложнее вычисления R(3, 3). Для больших параметров доказательства значительно усложняются. Дело в том, что не существует системного метода поиска чисел Рамсея (есть только грубые оценки), а с ростом параметров начинается очень обширное комбинаторное многообразие, не позволяющее найти решение даже компьютеру...

P.P.S. Практического применения чисел Рамсея нет, но в процессе их поиска было разработано масса полезного инструментария как в теории графов, так и в смежных областях.