V Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Теорема о четырёх красках
Автор работы награжден дипломом победителя I степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
«Мышление начинается с удивления» - заметил 2500 лет назад Аристотель.Наш современник Сухомлинский считал, что «Чувство удивления –могучий источник желания знать: от удивления к знаниям – один шаг».
ВВЕДЕНИЕ
Многие люди считают математику сухой и неинтересной наукой, которую сложно понять и часто задают вопрос преподавателю: «Зачем нужна математика?». С постановкой такого вопроса я не согласен. Мне всегда нравилось узнавать что-то новое и интересное, и когда я услышал на уроке геометрии, что существуют теоремы, которые до сих пор не доказаны, то решил посмотреть в интернете, что это за теоремы. Так, я в первые узнал о теореме о четырёх красках и решил изучить её подробнее и узнать где её можно применить в жизни.
Проблема исследования: Рассмотреть задачи, которые можно решить, применяя теорему о четырёх красках.
Цель проекта – рассмотреть практическое применение теоремы о четырёх красках.
Объект исследования - теорема о четырёх красках
Предмет исследования - задачи, решаемые с помощью теоремы о четырёх красках
Задачи исследования
1. Изучить историю возникновения проблемы четырёх красках, её практическое применение.
2. Рассмотреть задачи, решённые с помощью теоремы о четырёх красках.
3. Подобрать и решить задачи с помощью теоремы о четырёх красках.
4. Изготовить наглядные пособия, применяя теорему о четырёх красках
Основная часть
В 1852 году при раскрашивании карты Британии студент Френсис Гутри выдвинул гипотезу: что любую карту можно раскрасить четырьмя цветами, при условии, чтобы никакие две смежные области (имеющие общую границу) не оказались окрашенными в один и тот же цвет, Проблема возникла в том, чтобы решить, верна ли гипотеза!
Сам доказать её он не смог . Тогда он передал её через своего брата, тоже студента, известному английскому математику Августу Де Моргану. Так эта проблема дошла до математической общественности. И лишь после ее точной формулировки, другим английским математиком Артуром Кэли Год (1878) стал считаться годом рождения проблемы четырёх красок.
Её доказательство длилось более ста лет. В этот период была основана новая ветвь в математики – Топология. Которая изучает в частности — свойства геометрических фигур, которые остаются неизменными при непрерывных деформациях. Было найдено решение этой задачи для карт, расположенных на поверхностях сложной формы. Также было найдено верное доказательство того, что для любой карты достаточно пяти цветов; были обнаружены характерные свойства карт, для раскраски которых достаточно всего двух или трех красок, но сама задача так и не поддавалась доказательству. Ее неприступность объяснялась тем, что с ростом числа рассматриваемых стран на карте, лавинообразно росло число вариантов их раскраски, что затрудняло проверить правильность решения. Слишком большой был объём. И лишь в 1976 Кеннет Аппель иВольфганг Хакен из Иллинойского университета смогли доказать гипотезу. На помощь математикам пришли Компьютеры.
Задача о четырёх красках стала первой задачей в доказательстве которой применили неклассическое доказательство.(было рассмотрено 1936 карт, 400 страниц вычислений). В честь такого события, Почтой США была выпущена Марка с фразой "Четырёх цветов достаточно". .
И, т.к. классического её доказательства до сих пор ещё нет (доказано пока для 41 страны), то она попала в число семи математических задач тысячелетия, за решение которых Институт Клэя предлагает приз в 1 млн долларов .
Практическая часть
Эта история побудила меня поставить перед собой вопрос : "А смогу ли я раскрасить карту четырьмя красками, да так, чтобы ни одна из примыкающих соседних к ней областей не имела один и тот же цвет?"( с поправкой: точка их соприкосновения не считается общей границей). Раскрашивая карту Московской области, состоящей из 41 области, я сначала раскрашивал её в произвольной форме , без какой либо системы. И каждый раз я терпел неудачу. Тогда я решил начать с любой области и вокруг неё по часовой стрелке раскрашивал соседние смежные области (области с общей границей),так каждый раз расширяя круг на новые области. И у меня получилось(см. Приложение 1).
Но этого мало для такого утверждения. Мне предстоит рассмотреть и другие варианты карт. Проанализировав свои раскраски, я заметил, что каждый раз я раскрашивал область состоящую из четырёх областей, каждая из которых примыкала к трём другим .Иначе можно сказать, что они смежные (Область непосредственно примыкающая к границе других областей называют смежной)
Пример на рисунке:
Ещё одно наблюдение я сделал, раскрашивая карту, это то, что двух, трёх красок мне было недостаточно для моего условия задачи, пяти красок было вполне достаточно.
Но вопрос стоял о четырех красках.
Перед собой я поставил следующую задачу: Сколько стран могут коснуться друг друга напрямую, чтобы все страны имели общие смежные границы? И, сколько потребуется красок для их раскраски? «Форма» стран может отличаться от приведенных примеров, страны взаимосмежны.
1 вариант: две страны могут коснуться друг друга напрямую. Очевидно, что нам нужны 2 цвета.
Есть ровно 2 возможности, когда 1 или 2 страны расположены на внешней границе.
2 вариант: 3 страны могут коснуться напрямую и сходящиеся в одной точке.
Поскольку у всех стран есть 2 соседние страны, нам нужно 3 цвета.
Существует 3 различных варианта, где на внешней границе расположены 1, 2 или 3 страны.
3 вариант:Также возможно, что 4 страны сходящиеся в одной точке: в этом случае потребуется 2 цвета, но осталось только 2 варианта. Поскольку каждая страна имеет 3 соседние страны,нам нужно 4 цвета.
Отвечая на вопрос сколько стран напрямую примыкают друг к другу (т.е.каждая страна имеет общую границу с другими), я могу ответить, что максимальное число таких стран – 4.
А вот дальше для красок следовала закономерность: (рис. а) для n четных разбиений хватало 3 красок (это для карт образованных двумя концентрических окружностями) И для карт с нечетным числом стран сходящимися в одной точке, для n нечетных разбиений (рис. б) 4 красок (для карт образованных двумя концентрическими окружностями). Здесь хочу отметить что для карт с четным числом стран (сходящимися в одной точке) 4 и больше всегда 2 цвета
Мой вывод следующий: Раскрашивая карты с различным числом смежных стран, будут встречаться преимущественно 2-х, 3-х цветные. Иногда понадобиться 4-й цвет. А пятый -никогда.
Чтобы двигаться дальше мне потребовалось некоторые уточнения в формулировках терминов, т. к. Рассматриваемая теорема о четырёх красках относится к новой ветви математики- Топологии, то некоторые математические понятия надо уточнить: что называют картой в топологии
Определение: картой называется некая область на плоскости образованная разбиением ее на части (называемые странами) регулярным образом примыкающих друг к другу и имеющие границы.
Далее, изменив форму карты, я хотел ответить на вопрос: как повлияет изменение формы карты на ее раскраску?
Мой вывод следующий - для задачи раскрашивания карты неважно, какими являются границы стран, прямыми или нет. Карту можно немного растягивать, сжимать, искривлять стороны, и при этом число красок, необходимых для ее правильного раскрашивания, не изменится. На рисунке показана многоугольная карта и карта, полученная из нее искривлением сторон. В моем случае, везде потребуется 3 краски. Форма наших карт, не влияет на раскраску.
Экспериментируя с раскрасками , я наткнулся на следующий вопрос : а если некую карту разделить прямой, то что в результате получится, сколько красок потребуется -в данном случае ответ очевиден: потребуется два цвета, а, если несколькими пересекающимися прямыми, что получится, и сколько цветов для её раскраски потребуется?
Док-во: Предположим: Всякую карту, образованную прямыми, можно раскрасить в два цвета. Ясно, что карту, образованную одной прямой можно раскрасить в два цвета (рис. 2,а). Докажем, что если карта, образованная прямыми, раскрашена в два цвета, то карта, полученная из нее добавлением новой прямой также может быть раскрашена в два цвета (рис. 2,б). Действительно, новая прямая делит раскрашенную карту на две карты, каждая из которых раскрашена в два цвета. Причем к самой прямой примыкают пары областей, закрашенные в один цвет. Перекрасим одну из карт-половинок (безразлично, какую именно), изменив цвет каждой области на противоположный. Получим раскраску в два цвета всей карты (рис. 2,в). Поскольку любую карту, образованную прямыми можно получить последовательным добавлением прямых, то всякая такая карта может быть раскрашена в два цвета
Это есть Теорема о двух красках.
Дальше я рассмотрел вариант для двух, трёх пересекающихся окружностей. Докажем, что любую карту, образованную окружностями можно раскрасить двумя цветами:
Окр.1 , и Окр.2 есть замкнутые карты. При пересечении Окр.1 окружностью Окр.2, Окр.2 делит Окр.1 на две карты , линией пересечения является граница Окр.2. Очевидно, что карту Окр.1 можно раскрасить в два цвета.
Также можно сказать и про карту Окр.2, что Окр.1 делит Окр.2 на две карты, линией пересечения является граница Окр.1 и очевидно которую тоже можно раскрасить в два цвета.
В результате пересечения окружностей Окр.1 и Окр.2, мы получили три замкнутые области область- 1 Окр.1 , общую область-2 Окр.1 и Окр.2, и область-3 Окр.2, которые можно раскрасить двумя цветами (например, красный и синий) следующим образом: область-1 Окр.1 в красный цвет, общую область-2 зеркально в синий цвет, область-3 Окр.2 зеркально в красный цвет.
Таким образом, мы получили карту образованную двумя окружностями, раскрашенную двумя цветами.
Рассмотрим теперь карту, образованную тремя взаимно пересекающимися окружностями:Окр.1, Окр.2, и Окр.3. Окр.3 разделила карту1 полученную пересечением двух окружностей(Окр.1 и Окр.2) на две части. На рисунке видно, что Окр.3 пересекла области 1. 2. 3. принадлежащие первой карте. И разделила их на две части. В результате образовались области 4 .5 .6. А вот про область 7 можно сказать, что она получилась в результате пересечения первой карты с Окр.3.
В результате я получил вторую карту, образованную взаимным пересечение трех окружностей. Осталось раскрасить ее применяя зеркальный способ в два цвета.
И вновь, все области раскрашены в разные цвета.
Так же в рассматриваемых случаях для карт образованных последовательно добавлением четвёртой, пятой окружности, в результате каждый раз новая окружность делит карту на две части и после зеркального раскрашивания в два цвета получаем новую карту ,мы видим, что такую карту всегда можно раскрасить в два цвета.
Отсюда можно сказать, что любую карту образованную n- окружностями можно раскрасить двумя цветами.
Используя вопрос о том, какие свойства прямых и окружностей ,доказанных выше, используются при раскрашивании карт двумя цветами , можно ответить на вопрос: можно ли раскрасить двумя цветами карту образованную а) параболами, б) эллипсами
Мой ответ да и для парабол и для эллипсов. Т. к. при раскрашивании карт двумя цветами используются свойства: прямые и окружности делят карту (плоскость) на две части, такую карту можно раскрасить двумя цветами применяя так называемый зеркальный способ раскраски. Это свойство выполняется и для парабол и для эллипсов. Откуда следует, что карту образованную этими фигурами, можно раскрасить в два цвета. Двух красок достаточно для раскрашивания карты, образованной либо линиями, идущими от одного края листа до другого, либо замкнутыми кривыми. Проведя еще одну кривую, пересекающую всю карту от одного ее края до другого, мы должны, как и прежде, изменить все цвета по одну сторону от кривой на противоположные. Если вновь проведенная кривая замкнута, то изменить нужно окраску всех областей, попавших внутрь кривой, или, если угодно, всех областей, оказавшихся снаружи. Замкнутые кривые могут иметь и точки самопересечения, но в этом случае перекрашивание областей более сложное.
А вот вариант с пересекающимися окружностями содержащими хорды, показал практически, что в этом случае достаточно 3 цветов. На плоскости нарисовано n окружностей. В каждой окружности проведено по хорде так, что хорды двух окружностей имеют между собой самое большое одну общую точку. На рисунке показано, что получившуюся карту всегда можно раскрасить тремя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета.
Раз у меня получилось раскрасить географическую карту минимальным числом красок, возник вопрос, про раскраску геометрических фигур. Сколько цветов хватит для раскраски карт состоящих из многоугольников. Как было сказано ранее , что определение многоугольника в топологии не отличается от геометрического определения, отличается лишь названием : стороны- это границы, вершина - это точка в которой сходятся границы, геометрическая фигура - это страна, множество стран примыкающих друг другу - это карта.
Сначала, я рассмотрел такие карты на плоскости, потом усложнил задачу, рассмотрев карты образованные правильными многогранниками.
Используя уже имеющиеся знания о раскраске карт, я попробовал рассмотреть более сложные карты, составленные из многоугольников, заполняющих всю плоскость. Как и раньше требуется, чтобы любые два многоугольника или не имели общих точек, или имели общие вершины, или имели общие стороны.
Примеры таких карт дают паркеты, некоторые из которых представлены на рисунке
Раскрашивая эти карты, я придерживался следующего моего вывода: . для того чтобы определить сколько цветов для раскраски потребуется, надо определить (просто посчитать) сколько областей-стран примыкают друг к другу имея смежные границы. Для этого надо найти любую вершину внутри карты и посчитать, сколько стран подходит к ней.
И вот, что получилось: первая карта это в общем виде шахматная карта. Она получена путем разбиения ее прямыми линиями от начала и до конца (это теорема о двух красках). И для нее потребуется две краски.
Вторая карта тоже образована пересечением прямых от начала и до конца. И по теореме о двух краска эта карта раскрашивается двумя цветами.
В третьей карте я нашел страны примыкающие друг к другу, сходящиеся в одной вершине, их три, следовательно для раскраски понадобится три краски.
Ну и наконец, я перешёл к многогранникам: вопрос стоит тот же: сколько цветов для раскраски потребуется для каждого многогранника?
На рисунке показаны карты, образованные поверхностями правильных многогранников:
тетраэдра, куба(гексаэдр), октаэдра, икосаэдра и додекаэдра. Это их греческое наименование по числу граней.
Поверхность многогранника можно рассматривать как карту, странами которой являются грани многогранника, а границами - его ребра. Существует только пять правильных многогранников.
Многогранник называется топологически правильным, если его гранями являются многоугольники с одним и тем же числом сторон и в каждой вершине сходится одинаковое число граней.
Для ответа на поставленный вопрос, мне пришлось изучить каждый многогранник: из каких фигур они состоят, сколько граней(стран), сколько ребер(границ ), сколько вершин.
Тетраэдр: 4 грани(страны), 6 ребер(границ), 4 вершины, число ребер(границ) при вершине 3, число сторон у грани 3.
Куб(гексаэдр): 6граней(стран), 12ребер(границ), 8вершин, число ребер(границ) при вершине 3, число сторон у грани 4.
Октаэдр: 8 граней(стран), 12 ребер(границ), 6 вершин, число ребер(границ) при вершине 4, число сторон у грани 3.
Икосаэдр:20граней(стран), 30ребер(границ), 12вершин,число ребер(границ) при вершине 5, число сторон у грани 3.
Додекаэдр:12граней(стран),30 ребер(границ),20вершин, число ребер(границ) при вершине 3, число сторон у грани 5.
Т.к в топологии все фигуры можно рассматривать как карту, состоящую из стран примыкающих друг к другу, карты на плоскости и в пространстве эквивалентны(идентичны) и изменение формы границ не влияет на рас краску, я перенёс карту многогранника на плоскость сначала в виде таблиц: и рассматривал их как карту.
Сплошной цвет в таблице – это основание многогранника
Разделения на части – это грани многогранника
Применив раскраску на плоскости вот что получилось:
Раскрашивая эти карты я рассуждал так:
Для тетраэра: условно я разделил его на две области:
1.основание
2. область состоящую из трех частей(по числу граней) примыкающих друг к другу. Очевидно что здесь понаобятся 3 цвета.
Для куба: я разделил куб на три части:
1.верхнее основание,
2.средняя часть разделенная на четыре части(по числу граней). Примыкающие друг к другу
3 нижнее основание
Здесь видно, что средняя часть разделяет основания.То основания имеют один и тот же цвет.А средняя часть имеет четыре области примыкающие друг к другу, очевидно применим два цвета, но отличные от оснований. Следовательно всего потребуется 3 цвета.
Для октаэдра: я разделид его на две части: Каждая разделена на четыре части по числу граней. Здесь понадобилось 2 цвета.
Для икосаэдра: разделил на три части, каждая разделена по числу граней соответсвенно своей части.
1 часть разделена на 5 частей по числу граней
2 часть разделена на 10 частей по числу граней. Причем мне удобно было сохранить треугольную форму частей.
3 часть разделена на 5 частей по числу граней.
Здесь мне понадобилось 3 цвета.
Для додекаэдра: четыре части:
1.часть верхнее основание
2.часть разделена на 5 частей по числу граней
3.часть разделена на 5 частей по числу граней
4. часть нижнее основание
Для раскраски мне понадобилось 4 цвета.
Для ответа на вопрос сколько красок потребуется для раскраски карт, изучив доказательства и примеры решения задач, я выделил следующие правила:
Для плоскостных карты
2 краски, если карта разбита линией прямой , волнистой, овалом, окружностями
2 краски, если во внутренней вершине карты сходится четное число сторон(стран) ( например раскраска паркетов: 4 стороны)
3 краски , если n разбиений четно(концентрические окружности) и (нечетное число стран при вершине)
( например раскраска паркетов: 3 стороны, 5 сторон)
4 краски, если n разбиений нечетно(для концентрических окружностей)
И если четное число стран при вершине 4 и больше то всегда 2 краски
Для Многогранников:
2 краски - если в каждой вершине сходится 4 ребра
3 краски - если в каждой вершине сходится 3 ребра, каждая грань имеет четное число сторон.
3 краски - если в каждой вершине сходится нечетное количество рёбер >3, и грани имеют нечетное число сторон
4 краски - если в каждой вершине сходится 3 ребра, грани имеют четное +нечетное число сторон=нечетное число сторон.
Применяя полученные знания. Я изготвил макеты многогранников. Для этого я сначала раскрасил их развертки (см. Положение 2)
ЗАКЛЮЧЕНИЕ
Раскрашивая контурную карту цветными красками я и не предполагал, что когда мн задали вопрос: " А хватит ли мне четырёх разных цветных карандаша для раскраски карты, да так, чтобы границы смежных областей были раскрашены в разные цвета?", что передо мной приоткрылась дверь в неизведанный ещё мне мир математики.
Для ответа на поставленный, казалось бы ,очень простой вопрос, я подробнее познакомился с теоремой о четырёх красках. Начиная с её истории возникновения и её практического применения.
Раскрашивать карту четырьмя красками оказалось очень увлекательной задачей. Потребовалось проявить максимум внимания и умение предвидеть результат на несколько шагов вперёд. Найти оптимальные способы раскраски. И на практике применить полученные знания.
Не применяя каких либо формул, я убедился в правильности доказательства теоремы. А именно: любую географическую карту на плоскости (или на глобусе) можно правильно закрасить четырьмя красками. При этом Раскраска карты называется правильной, если любые стороны, имеющие на карте общую границу, окрашены в разные цвета. Наши исследования наглядно ответили на этот вопрос. ( У меня получилось раскрасить карту Московской области состоящей из 41области, карту России). Также я сделал макеты правильных многоугольников и раскрасил их минимально возможным количеством цветов.
Продвигаясь в своих исследований я узнал, что картой может называться не только географическая, но и любая область разбитая на части, регулярным образом примыкающие друг к другу. Что максимальное число стран напрямую примыкающих друг к другу 4.
Что есть карты для раскраски которых достаточно 2-х, 3-х, 4-х красок.
Главное, она дала старт новому разделу математики- Топологии - науке изучающей устойчивые свойства предметов при любых деформаций без разрывов. Иначе её называют пластилиновой геометрией, где чашка и бублик неотличимы друг от друга. С этим мне ещё предстоит познакомится. С миром пространства и абстракции. И после этого, стоит ли задавать вопрос: зачем нужна математика?
Информационные ресурсы:
1. Википедия
2. Л. Беве, Любая карта на плоскости может быть раскрашена в четыре цвета, Квант,1977 г., №1;
3. И. Шарыгин, Л. Ерганжиева, Наглядная геометрия, 5-6 кл., М, Дрофа, 2007 г.
4. Самохин А. В. Проблема четырех красок: неоконченная история доказательства //СОЖ. — 2000. — № 7. — С. 91—96.
5. Рингель Г. Теорема о раскраске карт / Перевод с английского В. Б. Алексеева. — М.:Мир, 1977. — 256 с. — книга с доказательством проблемы для всех поверхностей, кроме плоскости и сферы
6. Смирнов В.А. Смирнова И.М. Геометрия 7-9 классы
7. Барр Ст. Россыпи головоломок. – М.: Мир, 1987.
8. Болл У., Коксетер Г. Математические эссе и развлечения. – М.: Мир, 1986
9. Болтянский В.Г., Ефремович В.А. Наглядная топология. – М.: Наука, 1982 /Библиотечка “Квант”, выпуск 21.
10. Гарднер М. Математические головоломки и развлечения. – М.: Мир, 1971.
11. Дынкин Е.Б. и др. Математические задачи. – М.: Наука, 1971 /Библиотечка физико-математической школы, выпуск 1*.
12. Курант Р., Роббинс Г. Что такое математика? 2-е изд. М.: Просвещение, 1967.
13. Радемахер Г., Теплиц О. Числа и фигуры. – М.: Наука, 1966.
14. Саркисян А.А., Колягин Ю.М. Познакомьтесь с топологией. – М.: Просвещение, 1976.
15. Смирнова И.М. В мире многогранников. – М.: Просвещение, 1995.
16. Статьи из журнала //Квант:1971. № 4. С.61
1977. - № 1. – С.60
1974. - № 2. – С.58
1974. - № 4. – С.23
1972. - № 4. – С.30
Приложение 1. Карта Московской области, раскрашенная четырьмя красками
Приложение 2. Развёртки многогранников.