Category: наука

Category was added automatically. Read all entries about "наука".

Теорема Ферма на youtube

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



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

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

Теорема Ферма из Узбекистана

В новостях появились сообщения об очередном ученом, доказавшем теорему Ферма элементарными методами.

«Ташкентский математик Борис Пономарев утверждает, что нашел «простое оригинальное доказательство» Великой теоремы Ферма, над которым ученые мира бьются на протяжении 350-ти лет.»

http://www.12.uz/ru/news/show/education/8148/

Доказательство (включая обязательные у ферматиков историю теоремы и числовые примеры) занимает всего 7 страниц и выложено на сайте автора.

http://ponomarev-nz.narod.ru/



Ошибка наблюдается уже на 4-й странице (неверно самое первое утверждение, хотя снабжено числовыми примерами).


После этой ошибки говорить о доказательстве уже не приходится. Так что

«Я ознакомил с результатами своей работы коллег, получил их положительные отзывы, - говорит математик. – Жду ответа из академических институтов России, Европы и США».

...ожидания будут тщетными.

Отдельные ссылки на все страницы текста:
http://fotki.yandex.ru/users/ponomarev-nz/view/545596/?page=0
http://fotki.yandex.ru/users/ponomarev-nz/view/545597/?page=0#preview
http://fotki.yandex.ru/users/ponomarev-nz/view/545598/?page=0#preview
http://fotki.yandex.ru/users/ponomarev-nz/view/545599/?page=0#preview
http://fotki.yandex.ru/users/ponomarev-nz/view/545600/?page=0#preview
http://fotki.yandex.ru/users/ponomarev-nz/view/545601/?page=0#preview
http://fotki.yandex.ru/users/ponomarev-nz/view/545602/?page=0#preview

Ферматики на форуме мехмата

Форум мехмата превращается в помойку?

Топовая веточка (> 1200 постов):
http://www.mathforum.ru/forum/read/1/20535/

+ еще одна, в меньшей степени, но все же:
http://www.mathforum.ru/forum/read/1/624/

Цитировать это бессмысленно, математики там нет, но с недавнего времени особенно в первой ветке - откровенный дурдом. Так бывает, если полный бред не банят сразу.

R(4, 4). Шаг 1

Нахождения этого числа Рамсея - элементарная процедура.

По теореме Рамсея R(r, b) <= R(r - 1, b) + R(r, b - 1), тогда R(4, 4) <= 2 * R(3, 4) = 18.

Существует же раскраска полного графа с 17 вершинами, такая, что в графе не найдется ни полного красного подграфа с 4 вершинами, ни полного синего подграфа с 4 вершинами.



Таким образом R(4, 4) = 18.

Вопрос же о том, бывают ли другие (не изоморфные данному) такие графы, гораздо более сложный. Я оставлю его на какое-то время. Напишу только, что этот вопрос можно пытаться прояснить аналитически, так как искомый граф обладает массой свойств (регулярный, гамильтонов, возможно автоморфный), к тому же для него фиксирована окрестность любой вершины. Но об этом позже.

Задачка о цапле

Пусть дан связный ненаправленный невзвешенный граф в узком смысле (то есть без петель и кратных ребер). В нем выделены две вершины: A и B.

Пойдем по порядку.

I. Найти кратчайший путь, соединяющий данные вершины.

Это просто задача обхода графа в ширину, начиная с одной из выделенных вершин. Алгоритм линеен по числу ребер и вершин.

II. Найти кратчайший ЧЕТНЫЙ путь, соединяющий данные вершины.

Для этой задачи также есть простое решение. Сначала для каждой вершины v (будем ее называть также v0) создадим копию v1. После этого каждому ребру (u, v) сопоставим два ребра (u0, v1) и (u1, v0). На рисунке ниже ребра исходного графа изображены черным цветом, а построенные новые ребра - серым. После этого найдем кратчайший путь из A0 в B0. Соответствующий ему путь в исходном графе удовлетворяет требованиям задачи. Алгоритм также линеен по числу ребер и вершин.

III. Найти кратчайший ПРОСТОЙ ЧЕТНЫЙ путь, соединяющий данные вершины.

А вот тут уже все сложнее. Пока у меня есть некоторые наметки, но до конца еще не довел.

P.S.
Цапля тут при том, что в исходной задаче по кочкам ходила цапля и она должна была на кочку B прийти той же лапой, что стояла на кочке A.

Ниспровержение матана

Недавно наткнулся на одном из форумов на очередного ниспровергателя (некто Мишин). Приведу бувкально пару скринов из его "теории" (если кому-то интересно - ниже несколько ссылок, где можно почитать целиком).





Вот собственно и все. Ну недоучил человек в свое время пределы.

Дальше будут приводиться цитаты с форумов и из блога.

«О какой точке разрыва Вы толкуете? Разрыва ГРАФИКА ФУНКЦИИ? Но линия графика функции - не есть функция! Дайте мне определение функции, а затем определение функции с разрывом!»

Следовательно непрерывность функции тоже недоучил.

«Давайте изъясняться однозначно! Вам требуется найти значение функции f(x) в точке x_0. Это очень просто: f(x_0). Как, по-Вашему, можно различить предельное значение от непредельного, если, по определению, каждому элементу y = f(x) ставится в соответствие единственный элемент x?!»

А может быть и не слышал об этом...

«Тогда у меня к Вам такой вопрос: "Каким образом ВЫГЛЯДИТ во множестве понятие РАЗРЫВ ФУНКЦИИ"? Приведите на примере табличной записи функции.»

Собственно и функции помнит только из программы начальной школы.

Вообще говоря, все проблемы у данного товарища таятся в следующей фразе:

«Приращение аргумента - есть разница между двумя его произвольными значениями.»

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

«Давайте поспорим на лимон баксов, что ЭТА ФОРМУЛА - ВЕРНАЯ!!! Да, нет такого определения!...пока нет!!! Могу Вам подарить для кандидатской! В учебники вставят! Прославитесь на века!»

«Я себе штат ещё не набрал. Надо же кому-то докторские степени получать. Мне одному материала слишком много.»


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

«Я лет пятнадцать самофинансировал свою научную работу по математике.»

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


Потом он решил написать Президенту.

«Эти мысли я изложил в письме на имя Президента РФ в мае 2009 года. Попутно приложил часть своей работы, которая не раскрывала ноу-хау, но была достаточно информоемкой для экспертизы.»

«наконец, пришел окончательный, как я понял позже, ответ в виде "Заключения Государственной экспертизы ФГУ НИИ РИНКЦЭ" (www.extech.ru).

В котором, в частности, сказано: "В материалах С.В. Мишина делается попытка привлечь внимание к тому, что классическое интегральное исчисление не всегда согласуется с реальными физическими явлениями...в результате могут возникать противоречия. Для их устранения автор предлагает "свое" интегральное исчисление...Материал С.В.Мишина пока не может претендовать на создание нового учебника взамен старых,так как в учебниках даются факты, обоснованные научной теорией, а таковой в материалах С.В.Мишина пока нет...пока в материалах С.В.Мишина еще идет накопление фактов.

Называть это методом преждевременно...появление в материалах С.В.Мишина действительно новых интерпрпетаций производной любопытно и может в будущем оказаться полезным...автору рекомендуется продолжить свои изыскания." И - всё! Как-будто я работник математического института и государство оплачивает мою научную деятельность.»


Видимо после этого заключения автор решил, что экспертиза что-то одобрила. Начинается подсчет денег...

«Запросто можно посадить весь мир на иглу авторского права, потому, что открытие в сфере, ОБЯЗАТЕЛЬНОЙ к обучению. Подтверждено госэкспертизой. Вложения нужны не для разработки, а для НАПИСАНИЯ учебника (копейки). Денег может приносить - "море" ! НАХРЕН никому не надо, хотя все вопят про "прорывы". Вот он - прорыв, БЕРИТЕ!»

Еще немного о непризнанном гении.

«Люди, вызубрившие наизусть учебники математики, и из-за этого мнящие себя интеллектуальной элитой человеческого гения на самом деле не только сами не способны к открытию чего-то нового, но и всячески пытаются не подпустить к науке творческих людей, чтобы не стала видна НАУЧНАЯ НЕСОСТОЯТЕЛЬНОСТЬ этих, обладающих научной властью, недоумков.»

К замечаниям данный товарищ очень нервно относится.

«Слышишь, ты или ведёшь себя по-человечески, или по-хамски дёргай на х...! Я открыл тему, это мой дом, ты приходишь в мой дом и начинаешь по-хамски обссыкать углы...как с тобой общаться?!
Если ты такой придурок, что не понимаешь: И производная и первообразная - функции!!!!!! Они равноправны!!!! Их разница состоит только в том, что они связаны друг с другом ФОРМУЛОЙ, в которой ТЫ САМ ОПРЕДЕЛЯЕШЬ АРГУМЕНТ СВЯЗИ между ними!!! Если ты тупой по-жизни, то это не моя вина, а вина матанализа в том, что тупые могут считать себя умными-математиками! Это грех матанализа перед человеческим интеллектом!!!»


Образец, на мой взгляд, классический.

«Мы будем рассматривать КОНКРЕТНЫЕ моменты противоречия структана и матана или нет?!»

Структан? Пожалуй, желающих нет.

Ссылки на блог автора и форумы:
http://mishin05.livejournal.com/965.html
http://www.newtheory.ru/mathematics/vvedenie-v-strukturniy-analiz-t671.html
http://mathhelpplanet.com/viewtopic.php?f=51&t=1872&st=0&sk=t&sd=a
http://www.mathforum.ru/forum/read/1/29090/29152/
http://dxdy.ru/topic38168.html

UPD.
Тут некоторым не нравится термин математический маньяк. Ну что ж, пусть будет просто ниспровергатель.

R(3, 3)

 R(3, 3) = 6

Про это я уже писал в посте http://r-aa.livejournal.com/13819.html.

Тут интересно другое - сколько существует раскрасок полного графа из 5 вершин таких, что в графе не окажется ни красных, ни синих треугольников.

Определение:
Красной степенью вершины (deg_r(v)) назовем количество инцидентных ей красных ребер, аналогочно вводится синяя степень (deg_b(v)).

Итак, получим все возможные раскраски. Пусть есть полный граф с 5 вершинами. В нем нет красных и синих треугольников. Из доказательства для R(3, 3) = 6 следует, что красная и синяя степень любой вершины равна 2. Здесь и далее я иногда буду опускать синие ребра (соответственно полный синий подграф будет заменяться на вполне несвязный подграф). Итак, красная степень всех вершин равна двум. Удалим все синие ребра. Очевидно, что граф останется связным. Также нетрудно видеть, что связный регулярный граф степени 2 гамильтонов. То есть простой цикл из красных ребер и есть единственно возможная раскраска.

Первая цифра степеней двоек и закон Бенфорда

Сегодня вспомнил одну школьную задачку: как часто степень двойки начинается с единицы?

В такой постановке задачка решается легко, приводить ее решение я не буду (вообще все, что не касается теории графов, доказывать не хочу), его можно найти например по ссылке http://ega-math.narod.ru/Quant/Powers.htm.

В общем рассматривается последовательность {2^n}. Если принять всю совокупность ее членов за единицу, то какая часть этой последовательности начинается с цифры 1 (предельный переход, бла-бла...). В общем и интуитивно понятно и можно вычитать из вышеприведенной ссылки, что ответ log(2).

Следом возникает вопрос, а какая часть этой последовательности начинается с двойки, тройки, ... , девятки. На одном из форумов, я нашел рассуждения на эту тему: http://www.sciteclibrary.ru/cgi-bin/yabb2/YaBB.pl?num=1061902534.

Итак, распределение первых цифр степеней двоек выглядит следующим образом:

1 --- log(2)
2 --- log(3) - log(2)
...
8 --- log(9) - log(8)
9 --- 1 - log(9)

Ниже приведен график зависимости первой цифры степени от показателя степени двойки.



После этого возникает вопрос: а что если брать не степени двоек, а степени троек? Ответ наверное также следуют из второй приведенной ссылки, однако я удивился, когда понял, что распределение от основания степени не зависит (так как ответ искал не аналитически, а программно). В общем и для степеней троек, пятерок или девяток распределение остается таким же (для десятки по понятным причинам оно другое).

Ниже приведу аналогичные графики для тройки и девятки:





Таким образом последовательности {a^n} удовлетворяют закону Бенфорда.

«Когда число случайным образом берется из большого объема данных, например из котировок акций, данных переписи, или научных данных, то какова вероятность того что первой цифрой этого числа будет "1"? Исключив возможность появления нуля, логично предположить что вероятность будет 1/9, или около 11.1%.

Если вы проверите эту гипотезу на реальных данных, то заметите, что вероятность первой "1" будет, как ни странно, около 30.1%, вероятность первой "2" составит около 17.6%, вероятность первой "3" около 12.4%, и далее вероятности будут уменьшаться, так что вероятность первой "9" составит всего 4.5%.

Это распределение соответствует правилу, по которому вероятность того, что первой цифрой окажется d вычисляется по формуле: pd = log10(1 + 1/d).»


Далее по закону Бенфорда по ссылкам:
http://translated.by/you/benford-s-law/into-ru/
http://dxdy.ru/topic20348.html

Числа Рамсея

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

Число Рамсея 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. Практического применения чисел Рамсея нет, но в процессе их поиска было разработано масса полезного инструментария как в теории графов, так и в смежных областях.

Код Прюфера

Продолжу тему хранения деревьев. Для кодирования структуры дерева можно использовать код Прюфера. Код является оптимальным по объему. Суть состоит в следующем:

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

Алгоритм кодирования:
V = [1, ... , n] - номера вершин дерева.
P = [ ] - массив с кодом, пока пустой.
Для i от 1 до n-2 выполняем последовательность шагов:
1. Выбираем из дерева висячую вершину с минимальным номером - vi.
2. Находим вершину wi - смежную с vi.
3. Присваиваем P[i] = wi.
4. Удаляем из дерева вершину vi.

Восстановление дерева труда не составляет.

Ниже приведен пример дерева и его код Прюфера (1, 5, 2, 6, 1, 6, 6, 3).


P.S. Кроме самого практического использования код Прюфера ценен тем, что из него прямо следуют теорема Кэли, а именно, что у полного графа с n вершинами количество пронумерованных остовов равно n^(n-2).