ПРОБЛЕМ ЧЕТИРИ БОЈЕ

Уобичајен

ПРОБЛЕМ ЧЕТИРИ БОЈЕ

Чак 150 година је низ аматера, решаваоца пузли, али и професионалних математичара покушавало да реши проблем бојења географских карата. Права је реткост да један математички задатак изазове толику пажњу шире јавности, и какве везе уопште имају географске карте, боје и математика?

Проблем

Замислите да пред собом имате географску карту која приказује регије на које је подељена одређена држава или државе неког континента. Природно је да суседне државе на тој карти буду обојене различитим бојама. Без обзира на то како карта изгледа, од колико се држава састоји и каквог су оне облика, четири различите боје биће сасвим довољне да се та карта обоји на жељени начин. Показало се да ово јасно и једноставно тврђење није било једноставно да се докаже.

Image4245

Проблем дакле гласи овако: може ли се било која карта обојити са највише четири боје тако да суседне државе буду различито обојене?

Звучи једноставно? И док покушавамо да замислимо, онако, на брзину, неку имагинарну карту на којој би ова тврђење одмах “пало у воду”, помишљамо: коме то уопште треба? Зар само зато да би географске карте биле мање шарене?

Међутим, као да је управо чињеница да од тврђења и нема превелике користи деловала као магнет за математичаре. Сви они, који су проблем схватили као занимљиву слагалицу или необичну мозгалицу коју је требало брзо решити, брзо су и одустали.

Како је све почело…

Проблем је први поставио британски математичар Francis Guthrie пре више од 150 година. Guthrie је открио да су му за бојење регионалне карте Енглеске довољне само четири боје, али није био сигуран да ли ово тврђење може да се генерализује. Замолио је свог млађег брата Фредерика за помоћ. Фредерик је у то време студирао на Универзитету у Лондону, па је свом професору Августу Де Моргану поставио питање може ли да докаже тврђење. Де Моргана је постављени проблем прилично заинтересовао. Он 23. октобра 1852. године пише писмо свом колеги и пријатељу, Вилијему Хамилтону у Даблин у којем наводи тврђење и даје пример из којег је очигледно да су четири боје неопходне. Међутим, јесу ли четири боје увек довољне? Ако је одговор на постављено питање негативан, требало би пронаћи контрапример, тј. барем једну карту за коју је потребно најмање пет различитих боја. Ако је ипак тврђење тачно, треба доказати да оно важи за сваку, чак и “најуврнутију” карту, била она стварна географска карта, или нека потпуно измишљена.

Four_Colour_Map_Example.svg

И Де Морган и Хамилтон били су угледни британски математичари и редовно су се дописивали више од 30 година. Међутим, Хамилтона проблем четири боје уопште није занимао. Прилично разочаран тиме, Де Морган пише и другим колегама, а у априлу 1860. га по први пут објављује у књижевном часопису Athenaeum. Тако за њега сазнају и математичари с друге стране Атлантика. Прича каже да се амерички математичар, филозоф и логичар Charles Sanders Pierce “заразио” проблемом, месецима је покушавао да га решии, а наводно га је и решио, само што његов доказ никад није објављен.

Прецизнија дефиниција проблема

Ако питање четири боје формулишемо у облику теореме одмах “добија на тежини”.

Теорема о четири боје: Свака карта може да се обоји са највише четири боје тако да су суседне државе обојене различито.

Тврђење мора да буде истинито за сваку карту, без изузетака.

Међутим, шта кажу математичари, шта је заправо карта? Како задани проблем да преведемо на математички језик? Главни “алат” којим ће се проблем решавати биће теорија графова.

Карта је целина која се састоји од међусобно повезаних држава или регија. Граница сваке државе је затворена крива линија која се може поделити на онолико делова — граничних линија, колико та држава има суседа. Две државе са заједничком границом називају се суседне државе.

Границе се састају у врховима или чворовима. Претпоставићемо да се у сваком чвору састају најмање три граничне линије, а ако се две државе додирују у једној тачки, тада смеју да се обоје истом бојом.

coloring31

Након Де Морганове смрти 1871. године, проблем четири боје на неко време пада у заборав, све док га 13.6.1878. године на угледном састанку Лондонског математичког друштва, Британац Arthur Cayley није поновно поставио. Arthur Cayley био је изврстан студент математике и понео је титулу најмлађег професора на Кембриџу у 19. веку. Cayley се искрено заинтересовао за проблем четири боје и 1878. године објављује први чланак о њему и то (сасвим разумљиво) у географском, а не математичком часопису. У чланку признаје да није успео да докаже Теорему, али долази до неколико за доказ важних закључака.

Покушао је да докаже математичком индукцијом, али је ту застао. Међутим, у помоћ прискаче чувени Леонард Ојлер. Захваљујући његовом проучавању полиедара и закључцима до којих је дошао стотињак година раније, доказ је ипак могао да напредује.

Кемпе решава проблем!

Све ово успева да схвати, повеже и добро проучи лондонски адвокат и математичар аматер Alfred Bray Kempe. Kempe је чуо за проблем четири боје 1878. године. Иако је дипломирао право 1872. године, био је страствени заљубљеник у математику те је био присутан на састанку Лондонског математичког друштва када је Arthur Cayley говорио о проблему. И само годину дана касније имао је његово решење!

Идеју свог доказа Кемпе је објавио средином 1879. године у часопису Nature,, а крајем исте године објављује цео доказ у часопису American Journal of Mathematics. Узимајући у обзир све досад наведене закључке, Кемпеова метода бојења било које карте може се описати у шест корака.

Наиме, ово је постао најпознатији погрешан доказ у историји математике! Заварао је већину математичара тог времена и требало је чак 11 година да се открије грешка! А пронашао ју је ексцентрични професор математике из Durhama, Percy John Heawood. Heawood је завршио два факултета на Оксфорду: математику и  класичне студије латинског, грчког и хебрејског. Још за време студија заинтересирао се за проблем бојења карата и проучавао је Кемпеов доказ. У јуну 1890. у часопису Quaterly Journal of Mathematics Heawood објављује чланак Map-colour Theorem у којем “руши” Кемпеов доказ. Грешка у доказу јавља се при самом крају. Алфред Кемпе јавно је признао грешку, 1891. Године на састанку Лондонског математичког друштва.

Сада је постало јасно како наоко једноставан проблем није било нимало једноставно решити.

Током времена појавио се велики број доказа и оповргаванја истих. Проблем је, коначно, решен, али уз употребу рачунара.

Важност теорема о четири боје највећа је у математици. Једноставност и елеганција постављеног тврђења изазвала је општи интерес, како међу математичарима, тако и међу аматерима. Растао је интерес за математику и откривена су бројна друга тврђења и теореме.

Настале су нове гране математике. Теорема о четири боје посебно је допринела  развоју комбинаторике и теорије графова.

Они које је ова тема заинтересовала, детаљније о доказима Теореме о четири боје могу да пронаћу у следећим радовима:

Четири су довољнa

Проблем четири боје

Покушајте да урадите следеће задатке.

Извори:

http://mis.element.hr/fajli/715/41-08.pdf
http://wp.me/a4NjUO-qv
Advertisements

Оставите одговор

Попуните детаље испод или притисните на иконицу да бисте се пријавили:

WordPress.com лого

Коментаришет користећи свој WordPress.com налог. Одјавите се / Промени )

Слика на Твитеру

Коментаришет користећи свој Twitter налог. Одјавите се / Промени )

Фејсбукова фотографија

Коментаришет користећи свој Facebook налог. Одјавите се / Промени )

Google+ photo

Коментаришет користећи свој Google+ налог. Одјавите се / Промени )

Повезивање са %s