Теория шести рукопожатий говорит, что каждый человек на земле связан с каждым другим через шесть рукопожатий, не более, — так коротки цепочки, которые нас связывают. Связи существуют не только между людьми, но и между задачками и математическими моделями; и эти связи тоже интересно наблюдать. Например, мы недавно видели, как связаны гармонический ряд и гипотеза Римана, — между ними всего три "рукопожатия".
Еще один пример — незадача от 5 мая.
Все натуральные числа раскрасили в два цвета. Докажите, что среди них можно так выбрать числа k, m и n одного цвета, что k:m=m:n.
Эту задачу можно решить без большой математики, хотя на первый взгляд она простой не кажется.
Игорь Эльман заметил, что от нашей незадачи "рукой подать" до очень красивого результата. Он тоже говорит, что задача сводится к поиску арифметической прогрессии, а потом предлагает применять теорему Ван-дер-Вардена.
Теорема Ван-дер-Вардена (1927 г.)
гласит, что арифметическая прогрессия найдется обязательно, и не только длины три, но и любой другой длины. Более того, можно раскрашивать числа не в два цвета, а в три, четыре... — в любое конечное число цветов; все равно найдется одноцветная арифметическая прогрессия любой длины.
А.Я.Хинчин относит эту теорему к жемчужинам теории чисел — это красивый, нетривиальный результат, доступный продвинутому школьнику. Хинчин включил эту теорему в свою небольшую книжечку "Три жемчужины теории чисел".
От теоремы Ван-дер-Вардена рукой подать до теоремы Семереди.
Она тоже о том, что найдется арифметическая прогрессия — в любом достаточно плотном подмножестве натуральных чисел.
Что такое плотность множества? Для каждого натурального N посчитаем, сколько точек множества меньше N, и разделим это количество на N; то есть найдем долю точек множества среди натуральных чисел, которые меньше N. Найдем верхний предел этой последовательности при N, стремящемся к бесконечности, — это и есть плотность множества. Так вот, если плотность положительная, то множество уже достаточно плотно для того, чтобы в нем нашлась арифметическая последовательность.
От теоремы Семереди рукой подать до серьезных задач современной математики. Об этом ясно и понятно рассказывает Илья Шкредов:
Например, она позволяет делать выводы о распределении простых чисел, которые много веков не поддавались усилиям математиков, Оказывается, среди простых чисел можно найти арифметические прогрессии любой длины.
Вернемся к теории шести рукопожатий. Представим себе граф, вершины которого — жители земли; ребра графа — знакомства. Теория шести рукопожатий говорит нам, что от каждого человека можно дойти до каждого не более чем по шести ребрам. Это не значит, что граф связей между нами — густая-прегустая однородная сеть ребер.
На самом деле в этом графе есть относительно небольшое количество вершин с обширными, многочисленными связями; они и помогают нам наводить мосты.
Если построить граф между задачами или моделями — какая с какой связаны, то тоже ведь будут выделяться некие узловые задачи и модели, которые связаны с многими другими. Например, треугольник Паскаля или числа Фибоначчи — они возникают в очень разных ситуациях. Какие еще примеры узловых моделей можно привести?