Курс состоит из нескольких жизненных сюжетов, каждый из которых разбирается "по косточкам" и, как выясняется, содержит внутри себя нетривиальное математическое ядро. Это ядро далее также бьётся на "элементарные частицы" - так, что у слушателей возникает понимание всех глубинных механизмов рассматриваемой ситуации. Сюжеты сгруппированы по смыслу: каждая группа сюжетов вращается вокруг одной и той же основополагающей математической идеи. Таких идей всего пять: инвариант, шаг через бесконечность, непрерывность физических процессов, самоподобие природы и нашего её восприятия, и, наконец, алгебраическая природа различных чисел. Курс предназначен для всех, кто хочет лучше представлять себе тот мир, в котором мы живём. Не имея никаких предварительных знаний, слушатели будут введены в курс дела: какая техника используется в математике ("абсолютное доказательство" как главное отличие математического знания от любого иного) и как строить рассуждения. Вскоре выйдет вторая часть, "Математика для энтузиастов", которую нужно будет уже изучать "с листочком бумаги и ручкой в руках". В ней встретится более нетривиальный материал, в том числе "приводные ремни" современной математики - "группы" и "поля". Кроме того, будут вскрыты весьма нетривиальные подоплёки многих школьных задач. Курс состоит из 6 недель и 6 контрольных работ по окончании каждой недели. Для успешного прохождения курса необходимо успешно преодолеть все 6 испытаний.
Хроматическое число плоскости
Loading...
Из курса от партнера Moscow Institute of Physics and Technology
Математика для всех
325 оценки
Из урока
Элементы комбинаторики
На пятой неделе вы познакомитесь с несколькими сюжетами из мира теории вероятности, комбинаторики и графов.
Познакомьтесь с преподавателями
Савватеев Алексей ВладимировичДоктор физико-математических наук
Кафедра дискретной математики МФТИ
Бычков Борис СергеевичКандидат физико-математический наук, младший научный сотрудник международной лаборитории теории представлений и математической физики НИУ ВШЭ
Кафедра дискретной математики
Одна нерешенная математическая проблема.
Хроматическое число плоскости.
[ЗВУК]
[ЗВУК]
Что такое хроматическое число плоскости?
Возьмем некоторое запрещенное расстояние.
Ну, например, вот такое.
И будем красить всю плоскость, бесконечную во все стороны,
в такое количество цветов, чтобы никакие две точки
вот на данном расстоянии не были одного цвета.
Вот такая задача, доступная любому детсадовцу для понимания.
То есть, какие бы две точки я ни рассмотрел, если между ними
расстояние равно вот данному запрещенному нами,
то они должны быть разного цвета.
сколько цветов нужно,
чтобы удалось покрасить плоскость с соблюдением этого условия?
Ну, давайте вначале поймем, что двух цветов недостаточно.
Ну тем самым, конечно, понять, что одного цвета недостаточно.
Если вы одним цветом всю плоскость раскрасите, вот, пожалуйста,
любые две точки на этом расстоянии уже одноцветные.
Почему недостаточно двух цветов?
Потому что можно нарисовать равносторонний треугольник
вот именно такого размера, то есть со стороной,
которая имеет длину, запрещенную нами.
Тогда вы никак не можете обойтись двумя цветами, потому что,
если вы попробуете обойтись двумя цветами, то ясно,
что какие-то две вершины будут одного цвета,
– это называется в математике принципом Дирихле – ну и всё,
и между ними запрещенное расстояние, всё – раскраска запрещенная.
Немножко более сложный вопрос о том, достаточно ли трёх цветов?
Оказывается, что и трёх цветов недостаточно.
Но здесь картинку надо слегка видоизменить, усложнить.
И еще провести некоторые логические рассуждения,
чтобы установить, что трёх цветов мало.
Доказывать это утверждение мы будем от противного.
Итак, предположим, что трёх цветов мне хватило.
Вот три цвета, я крашу как-то плоскость так,
что любая точка будет одного из этих трёх цветов,
и любые две точки, находящиеся на запрещенном расстоянии,
окажутся разного цвета.
Тогда вспомогательное утверждение состоит в том, что любой
равносторонний треугольник, вершины его, должны быть
покрашены в разные цвета.
То есть, если я нарисую на плоскости любой равносторонний треугольник,
они будут первый, второй,
третий цвет, если у нас всего три цвета, то они будут
соответственно, все цвета использовать.
Ну что же, я тогда возьму и сделаю следующее.
Я нарисую наш равносторонний треугольник
запрещенного размера, и к нему приставлю еще один,
ровно такой же равносторонний треугольник.
Получится ромбик.
В этом ромбе из четырех точек
целых пять отрезков одинаковой длины.
И лишь последний шестой отрезок – более длинный.
Что можно сказать про этот ромб?
Я утверждаю, что у такого ромба, причем у любого такого ромба,
потому что с точки зрения рассуждений,
которые я сейчас провожу, они ничем не отличаются;
у любого такого ромба противоположные точки одноцветны.
Почему?
Потому что, если мы предположили, что трёх цветов достаточно для
раскраски плоскости, если наша плоскость уже
раскрашена в три цвета, то тогда вот этот треугольник разноцветный,
значит, здесь и здесь у него два стальных цвета по сравнению с этим.
То есть, если это цвет № 1, то здесь – № 2 и здесь – № 3
или наоборот.
Но в этом случае этот цвет тоже должен быть № 1,
потому что он не может быть ни № 2, ни № 3.
А значит, эти два цвета одинаковые.
Но это верно для любого такого ромба.
Давайте я теперь возьму этот ромб и начну
его поворачивать вокруг вот этой точки.
Вот так вращать туда-сюда.
Что у меня происходит?
У меня вот эта вершина начинает двигаться
по окружности соответствующего радиуса.
Какого? Ну вот такого.
Давайте я сдвину её по окружности так,
чтобы вот это вот расстояние тоже стало равным запрещенному.
То есть я поверну ромбик немножко, получится вот такой вот ромбик.
И про него верно то же самое рассуждение:
вот эта вершина и вот эта должны быть одноцветные.
И вообще у любого такого ромба, повернутого на любой угол,
вот эта вершина должна быть того же цвета, что и центр
вот этой окружности, которую заметает
противоположная вершина ромба.
Ну и всё, значит, все вот эти точки должны быть одного цвета.
И, в частности, если я поверну ромб на расстояние,
чтобы эти две точки стали на запрещенном расстоянии,
то эти две точки окажутся одноцветными, что запрещено.
А значит, у нас противоречие, то есть трёх цветов недостаточно.
Если плоскость раскрасить в три цвета,
то всегда можно обнаружить две точки
на запрещенном расстоянии, которые будут одноцветными.
Хорошо, двух цветов недостаточно, и трёх тоже недостаточно.
Интересно, а скольких цветов заведомо достаточно?
заведомо достаточно семи цветов.
Рассмотрим следующую картинку.
Это стандартное разбиение плоскости на правильные шестиугольники.
На, такие, так сказать, «пчелиные соты».
Возьмем запрещенное расстояние немножко большим,
чем диаметр шестиугольника, то есть расстояние между
противоположными его вершинами, и одновременно меньшим,
чем расстояние между противоположными концами
трёхзвенной ломаной, которая идет от угла к углу одноцветных фигур.
Тогда совершенно очевидно, что эта раскраска будет правильной,
потому что в пределах одного шестиугольника
не будет реализовано ни одно запрещенное расстояние,
а от одного цвета до другого запрещенным расстоянием
мы тоже достать не можем – оно короче, чем расстояние
от одного шестиугольника до другого шестиугольника
того же самого цвета.
Поэтому семи цветов достаточно, а трёх цветов недостаточно.
а скольких цветов на самом деле достаточно?
Верно ли что, например, шести цветов всё еще недостаточно?
уже четырех цветов достаточно?
То есть ответ на вопрос «Скольких цветов достаточно?
Какое минимальное количество цветов нужно, чтобы раскрасить плоскость
с соблюдением этого условия?»
находится где-то в диапазоне от четырех до семи.
Это либо четыре, либо пять, либо шесть, либо семь.
Так вот, внимание, ответ на этот вопрос неизвестен науке!
Никому на свете!
И нет даже пока возможности сократить этот разрыв.
То есть ответ может быть равен четырем, пяти, шести или семи!
И никто на свете ничего больше про это не знает.
Это совершенно вопиющая ситуация, потому что задача чисто детсадовская.
И тем не менее, это открытая математическая проблема.
Может быть, кто-то из вас увлечется математикой,
изучит всё необходимое для решения этой задачи и решит её.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
