Не стигат четири цвята да се боядиса равнина

Геронтологът Обри де Грей реши математически проблем, нерешен над 60 години

НаукаOFFNews Последна промяна на 23 април 2018 в 10:21 19879 0

Тази диаграма на граф с 826 върха изисква поне пет цвята, за да се гарантира, че няма два свързани върха, които са с един и същи цвят. Olena Shmahalo/Quanta Magazine;

Британският математик-любител Обри де Грей за първи път за последните 60 години подобри резултата в решаването на известен математически проблем за хроматичното число на равнината.

Това число е най-малкият брой цветове, с които може така да се оцвети равнината, че да няма две точки с един и същи цвят на единица разстояние (например, сантиметър). Тази задача не трябва да се бърка с подобната, но вече решена задача за оцветяване на карти.

По-рано бе известно, че хроматичното число на равнината лежи между 4 и 7, но де Грей показа, че с 4 цвята не може да се оцвети равнината. Препринт на неговата работа е публикувана в arXiv.org, а сега се проверява от други математици.

В математическия свят съществува практиката известни учени или организации да съставят списъци с берешени задачи, актуални в момента. Такъв е списъкът на Института Клей със задачите на хилядолетието, за решаването на които организацията дава 1 милион долара. 

Сега в математически проблем - проблемът на Хадвигер-Нелсън (Hadwiger-Nelson) - за първи път от повече 60 години бе постигнат напредък от един любител математик, биолога Обри де Грей (Aubrey de Grey), посветил живота си да разбере как можем да живеем по-дълго и може би, вечно. 

Графове за оцветяване

През 1950 г.  Едуард Нелсън, тогава студент в Университета в Чикаго, зададе един привидно прост въпрос, който измъчи математиците в продължение на десетилетия. Представете си, казва той, граф - колекция от точки, свързани с линии. Уверете се, че всички линии са с една и съща дължина и че всичко е разположено в равнина. Сега оцветете всички точки , така че да няма две свързани точки с един и същи цвят. Нелсън пита: "Кой е най-малкия брой цветове, с които може да оцветите такъв граф, дори образуван чрез свързване на безкраен брой върхове?

Тази задача е позната сега като проблемът "Хаджигер-Нелсън" или проблема с намирането на хроматичните числа на равнината. Тя предизвикв интереса на много математици. Те бързо намалиха възможностите, като установиха, че безкраен граф може да бъде оцветен с не по-малко от четири и не повече от седем цвята. 

Wikimedia Commons

Лесно е да се докаже, че два цвята не са достатъчни за оцветяване на равнината. Нека нарисуваме нашата равнина в два цвята. После да построим равностранен триъгълник със страната на единица разстояние. Първият връх е син, вторият е червен. И какъв цвят трябва да е третият връх? Тъй като е на разстояние единица от първите два, той не може да бъде нито в синьо, нито в червено. Малко по-трудно е да се покаже, че три цвята са недостатъчни. За да се направи това, е необходимо да се построи т.нар. вретено на Мозер - да вземем един ромб, състоящ се от два съединени единични правилни триъгълника. Да направим копие на него и да го завъртим около един от върховете на ромба (да го наречем "горен"), като направим така, че разстоянието между двата долни върха е единица. Лесно е да се види като просто се опитаме да оцветим вретеното на Мозер, че трите цвята за тази фигура не стигат.

Доказването на оцветяването в седем цвята също е много просто - то повтаря пчелната пита. Достатъчно е само да се положи мрежа на пчелни кутийки от правилни шестоъгълници със страна 0,4.

Така отговорът е сведен до едно от чиската 4, 5, 6 или 7, но не бе постигнат напредък и проблемът остана нерешен. Някои изследователи доказаха няколко частични резултати през следващите десетилетия, но никой не успя да промени тези граници. Докато не се намеси Обри де Грей.

Биологът, който остави името си в математиката

Де Грей не е професионален математик, неговите интереси лежат повече в областта на геронтологията и проблемите на стареенето. Той ръководи фондацията SENS, която разработва стратегии за постигане на "премахване на негативните ефекти от стареенето" чрез инженерни методи. Биологът, който веднъж направи смелото твърдение, че хората, които живеят днес, ще живеят до 1000 години, де Грей обича да си почива от текущата си работа, като решава проблеми от математиката.

И успява. В статията си "Хроматичното число на равнината е най-малко 5" той демонстрира, че равнинен граф с разстояния единица не може да бъде оцветен само с четири цвята.

Решението на Де Грей е вдъхновено от играта на дъска "Отело" (наричана и Реверси), която напомня на играта "Го". Основният вариант се играе на квадратна дъска с квадрати 8 x 8. Целта на играта е да имаш повече фигури на дъската от своя противник. Играта приключва, когато всички квадратчета са заети с фигури или нито един от двамата противници на може да направи ход.

Играта "Отело". Paul_012 / Wikipedia

Преди десетина години де Грей като запален играч на "Отело" се среща с някои талантливи математици, които го запознават с теорията на графите и той се връща към нея от време на време. И около Коледа миналата година той прави пробива си.

"Понякога, когато имам нужда от почивка от истинската си работа, мислех за математика", коментира той в Quanta magazine

"Имах изключителен късмет - споделя де Грей. "Не всеки ден някой излиза с решение на 60-годишен проблем".

Четирицветната теорема

В статията си, де Грей е показал как да се изгради структура от 1567 върхове, които не могат да бъдат оцветени с четири цвята, така че няма две точки на единица разстояние, които да не са в един и същи цвят. Конструкцията се състои от четири стъпки.

Оцветяването отгоре съдържа монохромен триъгълник, а отдолу - не. Aubrey D.N.J. де Грей / arXiv.org, 2018

Да построим правилен шестоъгълник със страна единица, да поставим точка в центъра му и да я свържем с върховете, тя ще се намира на разстояние единица от всеки връх. Да се опитаме да го боядисаме в четири цвята по всички възможни начини. Оказва се, че има само четири коренно различни оцветявания на шестоъгълника, при това в две от тях се появяват равностранни триъгълници със страни, равни на корен квадратен от три, всички върхове на които са оцветени с един и същи цвят. Де Грей ги нарича монохромни тройки.


Основата за построяване на фигура, съдържаща най-малко една монохромна тройка. Aubrey D.N.J. de Grey / arXiv.org, 2018

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

Скелет от 52 шестоъгълника, в които гарантирано възникването на монохроматичн тройка. Aubrey D.N.J. де Грей / arXiv.org, 2018

Втората част на доказателството е да се построи граф, в който възниква шестоъгълник, в който при нито един вариант на оцветяване не може да има монохроматична тройка. Той се състои от голям брой специално разположени вретена на Мозер, които са разположени около един шестоъгълник и имат 1345 върха. В следващия етап на де Грей копира този граф 52 пъти, така че негова част да се окаже графът от  предходния абзац, в който непременно възниква монохромна тройка. Полученият скелет с 20425 върха не може да бъде оцветен в четири цвята, тъй като в противен случай възниква противоречие.

Скелет, в центъра на който гарантирано не може да възнике монохроматична тройка (вдясно). Валяво - първоначалната структура за построение. Aubrey D.N.J. de Grey / arXiv.org, 2018


Де Грей се опита да опрости този скелет, но най-добър резултат даде конструкция с 1567 върха, получена чрез премахване на част от точките. Но след последващата проверка се оказа, че все пак може да се боядиса в четири цвята, но след това  построява примера с 1581 върха, който не може да се оцвети с по-малко от 5 цвята. 

Ако изводът от статията де Грей се потвърди, че ще бъде един от редките случаи, когато трудна математическа задача, която е занимавала голям брой специалисти, се решава от математик-любител. Предишният случай, свързан с покриването на равнина с петоъгълмици, бе през 1976 г. и 1977 г. от Марджъри Райс, домакиня, без математическо образование.

Най-важното
Всички новини
За писането на коментар е необходима регистрация.
Моля, регистрирайте се от TУК!
Ако вече имате регистрация, натиснете ТУК!

Няма коментари към тази новина !