Математика для гуманитариев. Живые лекции - Алексей Владимирович Савватеев

17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4.

Заметьте, что от 17 уже довольно далеко до повторяющейся части. Сиракузский царь (или кто-то еще) перебрал первую тысячу чисел и обнаружил, что все они приходят к одинаковому концу, их всех ждет цикл «4 → 2 → 1». При этом для некоторых чисел цепочки получаются очень длинные, и числа в процессе преобразований достигают очень больших значений. Число 27 достигает 9232, приходит к циклу за 112 шагов. Вопрос: любое ли число придет к циклу? Ответ был (якобы) неизвестен 2500 лет назад, и до сих пор неизвестен. Конечно же, компьютеры давно запущены, и числа давно проверены до величины порядка 1015. Компьютер продолжает работать. Но все числа перебрать нельзя. И даже если бы компьютер не довел какое-то число до цикла — это не доказывает, что этого сделать нельзя. Возможно, цепочка просто очень длинная. Что в этой проблеме интересно? Вспомним теорему Ферма (для нее тоже получалась всё более длинная цепочка степеней «n», для которых она верна). Но ее доказали для любого «n» без помощи компьютера (в принципе, если бы компьютер предложил три числа x, у, z и степень «n», которые опровергли бы теорему Ферма, он бы решил проблему). А в нашем случае компьютер ничего не может. Разве сам только он найдет какой-то новый цикл!

В 1994 году Уайлз, готовясь к докладу, нашел ошибку в своем доказательстве «великой теоремы Ферма». К счастью, ошибка оказалась несущественной и была им исправлена. А 1 апреля ему пришло электронное письмо, в котором математик, известный Уайлзу, писал, что, пользуясь его методами, он опроверг теорему Ферма. В письме приводились числа и опровержение, содержащее маленькую, незаметную ошибку… У Уайлза был шок (он забыл про 1 апреля). К счастью, эта шутка оказалась не смертельной.

Но теорему Ферма в итоге долгих усилий доказали, а рассматриваемую нами — нет. Уже столько лет требуется человек (апрелеустойчивый), который это докажет.

Следующая по сложности проблема — тоже простая (по формулировке, конечно). Она поставлена сравнительно недавно. И я совершенно уверен, что ее скоро решат.

Давайте рассмотрим прямую линию. Можно ли раскрасить прямую линию в две краски так, чтобы точки на расстоянии единица всегда получались разноцветными? Ясно, что одного цвета недостаточно, а в два цвета раскрасить можно. Например, всю прямую можно разбить на полуотрезки длины 1 с отброшенным правым концом. И эти полуотрезки поочередно закрашивать то красным, то зеленым цветом.

Поэтому для прямой минимальное количество цветов, которое требуется, чтобы любые две точки на расстоянии 1 были разноцветными, равно двум. Соответствующее число для плоскости никому не известно.

Давайте рассмотрим некоторые начальные соображения. На плоскости есть равносторонний треугольник со стороной 1 (рис. 103). Закрашивая всю плоскость, мы, конечно, закрасим и всю площадь этого треугольника, и всю его границу — в частности, закрасим и все вершины этого треугольника.

Рис. 103. Выбираем самый трудный для закрашивания треугольник.

Сколько нам нужно цветов?

Слушатель: Хотя бы 3…

А.С.: Да, двух уже недостаточно. Иначе из трех вершин на расстоянии 1 друг от друга две окажутся одноцветными. Ведь этот треугольник специально взят таким, чтобы длины его сторон были «запрещенными».

Поэтому нужно хотя бы три разных цвета (скажем, К — красный, С — синий, 3 — зеленый). Представьте себе, что с трех сторон к этому треугольнику пририсованы такие же треугольники, затем еще и еще приклеиваем множество таких «особо трудных» треугольников, пока вся плоскость не окажется сплошь покрытой ими. (Математики в этом случае говорят так: рассмотрим на плоскости ТРЕУГОЛЬНЫЙ ПАРКЕТ.) Раскрасив правильным образом этот паркет цветами К, С, 3 (если бы нам это удалось), мы бы полностью решили поставленную задачу для плоскости. Вы, конечно, догадываетесь, что нам не удастся этого сделать (иначе бы эту задачу давно бы уже решили опытные математики). Но мы всё же попробуем это сделать возможно, от этого расширится горизонт наших знаний. Сначала раскрасим правильным образом только вершины 3-угольного паркета. Эти вершины образуют горизонтальные ряды на плоскости; в каждом ряду вершины смещены на 1/2 отношению к предыдущему (и последующему) ряду. Предлагается такой способ раскраски вершин в этих рядах (рис. 104).

Рис. 104

Как вы видите, каждые три ближайшие вершины закрашены разными цветами, как и должно быть по условию. Ведь расстояние между ними как раз равно 1. Обратите внимание, что третий ряд раскрасок совпадает с первым, четвертый со вторым, и т. д. до бесконечности. В данном случае (когда мы используем только три разных цвета) это не случайность — легко понять, что две вершины «через ребро» будут одноцветными (см. рис. 104). В самом деле, если разрешенных цветов только три, то для «отраженной» вершины просто нет выбора. Однако при любой попытке продолжить раскраску на ребра паркета (и далее на собственно плитки) нас постигнет неудача. Эта неудача не является случайной (из-за того или иного неверного подхода к этой задаче), а является следствием такой (уже доказанной) теоремы: Для правильного закрашивания плоскости заведомо не хватит трех красок. Доказано и полезное добавление к этой теореме: для успешного закрашивания заведомо хватит СЕМИ разных красок. Таким образом, в настоящее время известно следующее: минимальное количество красок для закрашивания плоскости равно либо 4, либо 5, либо 6, либо 7.

Эту теорему можно доказать вполне школьными вычислениями, и мы это сделаем — жалко было бы не познакомить вас с таким элегантным доказательством. (Его придумали братья Мозеры. Просто взяли и предъявили 7 конкретных точек на плоскости и доказали, что даже эти 7 точек НЕЛЬЗЯ закрасить тремя разными цветами. Значит, всю плоскость и подавно нельзя ими раскрасить. Эти семь точек образуют замысловатую конструкцию, похожую на два веретена, нижние концы которых соединены, а прочие два конца связаны веревочкой длины 1 (понятно, почему 1?). С тех пор в жаргоне математиков появилось звучное выражение «Веретено братьев Мозеров»).

Сейчас я покажу, что на самом деле нужно хотя бы 4 цвета.

Предположим, что мы можем раскрасить плоскость в 3 цвета. Тогда любой правильный треугольник будет разноцветным (в смысле окраски своих вершин), а значит, у ромба из двух таких треугольников (рис. 105) две противоположные вершины окажутся одного цвета. Вот и получилось первое веретено!

Рис. 105. Веретено. Будем вращать его вокруг нижней точки «К».

Повернем ромб вокруг одной из