html текст
All interests
  • All interests
  • Design
  • Food
  • Gadgets
  • Humor
  • News
  • Photo
  • Travel
  • Video
Click to see the next recommended page
Like it
Don't like
Add to Favorites

Математикам не хватило четырех цветов для раскраски плоскости


Граф, который не может быть раскрашен в четыре цвета так, чтобы на единичном расстоянии в нем не нашлось двух вершин одного цвета

Aubrey D.N.J. de Grey / arXiv.org, 2018

Британcкий математик-любитель Обри ди Грей впервые за последние 60 лет улучшил результат решения известной математической задачи о хроматическом числе плоскости. Это число — наименьшее количество красок, с помощью которых можно так раскрасить плоскость, чтобы на фиксированной единице расстояния (например, сантиметр) нигде не нашлось двух точек одинакового цвета. Эту задачу не стоит путать с похожей, но уже решенной задачей о раскрашивании карт. Раньше было известно, что хроматическое число плоскости лежит между четырьмя и семью включительно, а теперь Ди Грей показал, что в четыре цвета плоскость точно раскрасить нельзя. Препринт работы опубликован на arXiv.org, сейчас построение проверяется другими математиками.

Веретено Мозера и семицветная раскраска


Исторически задача о раскрашивании плоскости была сформулирована в 1940-х годах Эрдёшем и, независимо от него, в 1950 году Нелсоном. Легко показать, что двух цветов не достаточно для раскрашивания плоскости. Пусть мы раскрасили нашу плоскость в два цвета. Тогда возьмем на ней равносторонний треугольник со стороной в одну единицу расстояния. Первая вершина — синяя, вторая — красная. А какого цвета третья вершина? Так как она находится на расстоянии один от первых двух, то ни синей, ни красной она быть не может. Немного сложнее показать, что и трех красок недостаточно. Для этого нужно построить веретено Мозера: возьмем ромб, состоящий из двух склеенных между собой по стороне правильных единичных треугольников. Сделаем его копию и немного повернем ее вокруг одной из вершин ромба (назовем ее верхней), при этом сделаем так, что расстояние между двумя нижними вершинами стало единицей. Легко увидеть, просто попытавшись раскрасить веретено Мозера, что трех цветов для этой фигуры не хватает.

Возможная раскраска из семи цветов устроена очень просто: она повторяет пчелиные соты. Достаточно просто выложить соты из правильных шестиугольников со стороной в 0,4. До работы Обри ди Грея это были самые сильные ограничения на хроматическое число плоскости в течение последних 67 лет.

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

Раскраски сверху содержат монохроматический треугольник, снизу — нет

Aubrey D.N.J. de Grey / arXiv.org, 2018

Построим правильный шестиугольник с единичной стороной, поставим точку в его центре и соединим ее с вершинами — она находится на расстоянии единицы от вершин. Попытаемся раскрасить его в четыре цвета всеми возможными способами. Оказывается, есть всего лишь четыре принципиально различных раскраски шестиугольника, причем в двух из них возникают равносторонние треугольники со стороной равной квадратному корню из трех, все вершины которых окрашены в один цвет. Их ди Грей называет монохроматическими тройками.

Основа для построения фигуры, содержащей хотя бы одну монохроматическую тройку

Aubrey D.N.J. de Grey / arXiv.org, 2018

Оказывается, можно построить такой граф, в котором обязательно найдется монохроматическая тройка. Он будет состоять из 52 таких шестиугольников, правильным образом расположенных на плоскости. Вкратце, построение начинается с шестиугольника, построенного из шестиугольников из абзаца выше, который затем удваивается и поворачивается относительно центра, а затем относительно вершины, лежащей на расстоянии два от центра.

Каркас из 52 шестиугольников, в котором гарантированно возникнет монохроматическая тройка

Aubrey D.N.J. de Grey / arXiv.org, 2018

Вторая часть доказательства — построить граф, в котором возникнет шестиугольник, в котором ни при каких раскрасках не может возникнуть монохроматическая тройка. Он состоит из большого количества особым образом расположенных веретен Мозера, которые располагаются вокруг единичного шестиугольника и насчитывает 1345 вершин. На следующем этапе ди Грей копирует этот граф 52 раза так, чтобы его частью оказался граф из предыдущего абзаца, в котором монохроматическая тройка обязательно возникнет. Получившийся 20425-вершинный каркас нельзя раскрасить в четыре цвета, так как иначе возникает противоречие.

Каркас, в центре которого гарантированно не может возникнуть монохроматической тройки (справа, слева — исходная структура для построения)

Aubrey D.N.J. de Grey / arXiv.org, 2018

Ди Грей также попробовал упростить этот каркас, наилучшим результатом стала конструкция с 1567 вершинами, полученная удалением части точек.

Редакция N+1 обратилась за комментариями к математикам Андрею Райгородскому и Алексею Канелю-Белову, экспертам в этой области. По словам ученых, сейчас статью ди Грея проверяют компьютерными методами и полный прогон решения на компьютере может занять несколько дней. К проверке привлечены и школьники-олимпиадники, уточнил Канель-Белов.

Интересно, что точно та же задача может быть сформулирована и для пространств высших размерностей (трехмерного, четырехмерного и так далее). К примеру, для трех измерений границы хроматического числа установлены гораздо слабее — оно лежит между 6 и 15. Подробнее о хроматических числах можно почитать в брошюре Андрея Райгородского, изданной МЦНМО 15 лет назад. В общем случае задача не решена до сих пор. Более того, возможно, ее точное решение зависит от аксиоматики теории множеств.

Если утверждение статьи ди Грея подтвердится, то это будет один из редчайших случаев, когда в непростой математической проблеме, которой занималось большое число профессионалов, удалось продвинуться математику-любителю, рассказывает Константин Кноп, преподаватель и популяризатор математики из Санкт-Петербурга. Предыдущий такой случай был связан с замощением плоскости пятиугольными паркетами — в 1976 и 1977 годах новые замощения были открыты Марджори Райс, домохозяйкой без математического образования. А в 2017 году московский школьник-десятиклассник нашел новое ограничение в задаче Данцера и Грюнбаума об острых треугольниках в трехмерном пространстве, что подтолкнуло профессионалов к уточнению оценок в обобщенной задаче.

Обри ди Грей — не профессиональный математик, его интересы лежат скорее в области геронтологии и проблем старения. Он возглавляет фонд SENS, развивающий стратегии достижения пренебрежимого старения инженерными методами. 

В математике есть ещё одна, немного похожая задача — о раскрасках карт (иначе, проблема четырех красок). Она была решена Кеннетом Аппелем и Вольфгангом Хакеном в 1972 году компьютерными методами — математики показали, что для любой карты достаточно четырёх красок, чтобы никакие две области одного цвета не граничили друг с другом. Это стало первым компьютерным доказательством крупной математической теоремы.

Владимир Королёв

Читать дальше
Twitter
Одноклассники
Мой Мир

материал с nplus1.ru

3

      Add

      You can create thematic collections and keep, for instance, all recipes in one place so you will never lose them.

      No images found
      Previous Next 0 / 0
      500
      • Advertisement
      • Animals
      • Architecture
      • Art
      • Auto
      • Aviation
      • Books
      • Cartoons
      • Celebrities
      • Children
      • Culture
      • Design
      • Economics
      • Education
      • Entertainment
      • Fashion
      • Fitness
      • Food
      • Gadgets
      • Games
      • Health
      • History
      • Hobby
      • Humor
      • Interior
      • Moto
      • Movies
      • Music
      • Nature
      • News
      • Photo
      • Pictures
      • Politics
      • Psychology
      • Science
      • Society
      • Sport
      • Technology
      • Travel
      • Video
      • Weapons
      • Web
      • Work
        Submit
        Valid formats are JPG, PNG, GIF.
        Not more than 5 Мb, please.
        30
        surfingbird.ru/site/
        RSS format guidelines
        500
        • Advertisement
        • Animals
        • Architecture
        • Art
        • Auto
        • Aviation
        • Books
        • Cartoons
        • Celebrities
        • Children
        • Culture
        • Design
        • Economics
        • Education
        • Entertainment
        • Fashion
        • Fitness
        • Food
        • Gadgets
        • Games
        • Health
        • History
        • Hobby
        • Humor
        • Interior
        • Moto
        • Movies
        • Music
        • Nature
        • News
        • Photo
        • Pictures
        • Politics
        • Psychology
        • Science
        • Society
        • Sport
        • Technology
        • Travel
        • Video
        • Weapons
        • Web
        • Work

          Submit

          Thank you! Wait for moderation.

          Тебе это не нравится?

          You can block the domain, tag, user or channel, and we'll stop recommend it to you. You can always unblock them in your settings.

          • nplus1.ru
          • математика
          • ученые
          • домен nplus1.ru

          Get a link

          Спасибо, твоя жалоба принята.

          Log on to Surfingbird

          Recover
          Sign up

          or

          Welcome to Surfingbird.com!

          You'll find thousands of interesting pages, photos, and videos inside.
          Join!

          • Personal
            recommendations

          • Stash
            interesting and useful stuff

          • Anywhere,
            anytime

          Do we already know you? Login or restore the password.

          Close

          Add to collection

             

            Facebook

            Ваш профиль на рассмотрении, обновите страницу через несколько секунд

            Facebook

            К сожалению, вы не попадаете под условия акции