ˇ Paul Erd˝ os: Zivot v cit´ atech L’ubom´ıra Balkov´ a Proˇc jsou ˇc´ısla n´ adhern´ a? To je jako pt´ at se, proˇc je n´ adhern´ a Beethovenova Dev´ at´ a symfonie. Kdyˇz nev´ıte proˇc, nem˚ uˇze v´ am to nikdo vysvˇetlit. J´ a v´ım, ˇze ˇc´ısla jsou n´ adhern´ a. A jestli nejsou, tak potom nen´ı n´ adhern´e uˇz nic. Paul Erd˝os
Paul Erd˝ os (26. 3. 1913, Budapeˇsˇt - 20. 9. 1996, Varˇsava) je nejzn´amˇejˇs´ım matematikem 20. stolet´ı a jedn´ım z nejslavnˇejˇs´ıch matematik˚ u v˚ ubec. Tak´e je bez pˇreh´ anˇen´ı jednou z nejzaj´ımavˇejˇs´ıch postav nejen matematick´eho svˇeta. Kromˇe vlastn´ıch v´ ysledk˚ u a elegantn´ıch d˚ ukaz˚ u, kter´ ych m´a P. Erd˝os na sv´em kontˇe nepoˇc´ıtanˇe, mu n´ aleˇz´ı z´ asluha na zmˇenˇe stylu pr´ace v matematice. Zat´ımco do poloviny 20. stolet´ı publikovala vˇetˇsina matematik˚ u samostatnˇe, je dnes pˇres 50% ˇcl´ ank˚ u d´ıtˇetem spolupr´ ace. P. Erd˝os je autorem cca 1500 ˇcl´ank˚ u (coˇz je absolutn´ı rekord a na z´ ada mu d´ ychaj´ı pouze Leonhard Euler, Augustin-Louis Cauchy a Arthur Cayley), ale hlavnˇe tyto ˇcl´anky sepsal s v´ıce neˇz 500 spoluautory! Nen´ı divu, ˇze na jeho poˇcest bylo definov´ano Erd˝osovo ˇc´ıslo [5]: P. Erd˝os s´am m´a ˇc´ıslo 0, ti, kdo napsali ˇcl´ anek s P. Erd˝ osem, maj´ı ˇc´ıslo 1, ti, kdo publikovali ˇcl´anek s nˇejak´ ym spoluautorem P. Erd˝ ose, maj´ı ˇc´ıslo 2 atd. Existuje odhad, ˇze 90% aktivn´ıch matematik˚ u m´ a Erd˝ osovo ˇc´ıslo menˇs´ı neˇz 8. Erd˝osovu aktivitu tak´e dokl´ad´a pˇekn´a ˇr´adka vˇet a hypot´ez, kter´e nesou jeho jm´eno [4]. A jeˇstˇe jedno prvenstv´ı mu nelze upˇr´ıt. Snad o ˇz´ adn´em jin´em matematikovi nekoluje tolik cit´at˚ u jako pr´avˇe o P. Erd˝osovi. Cit´ aty Erd˝ osov´ ych v´ yrok˚ u (budou znaˇceny kurz´ıvou) a v´ yrok˚ u jeho pˇr´atel a koleg˚ u (oznaˇc´ıme je “uvozovkami”) lze popsat t´emˇeˇr cel´ y jeho ˇzivot. Budou ˇcasto ˇ st´ı matematici cituj´ı. ponech´ any v angliˇctinˇe, protoˇze pr´avˇe tak je dokonce i madarˇ
1
Z´ azraˇ cn´ e d´ıtˇ e
Jiˇz od u ´tl´eho dˇetstv´ı vˇedˇel Paul Erd˝os 1 , ˇze bude matematikem. Jako 4-let´ y ovl´adal z´ aporn´ a ˇc´ısla. Pˇr´ atele sv´e matky bavil t´ım, ˇze z hlavy podle jejich data narozen´ı poˇc´ıtal, kolik vteˇrin jsou na svˇetˇe. Kdyˇz mu bylo 10 let, otec mu uk´azal Eukleid˚ uv d˚ ukaz tvrzen´ı, ˇze prvoˇc´ısel je nekoneˇcnˇe mnoho. Paul byl okouzlen. Pozdˇeji jej zase ˇ nadchl Cantor˚ uv d˚ ukaz nespoˇcetnosti re´aln´ ych ˇc´ısel. Casto pak sv´e dopisy konˇcil 1 Madarsk´ ˇ a verze jm´ ena Pavel je P´ al, jelikoˇ z ale Paul Erd˝ os str´ avil vˇ etˇsinu ˇ zivota na cest´ ach, je zn´ am´ y pod anglickou verz´ı sv´ eho jm´ ena.
1
formulkou: Let the spirit of Cantor be with you. Pˇr´ıpadnˇe zkr´acenou verz´ı: C. be with you. Pr´ avˇe hled´ an´ı elegantn´ıch d˚ ukaz˚ u se stalo smyslem jeho ˇzivota. ˇ Poprv´e okouzlil P. Erd˝ os madarsk´ e matematick´e kruhy jako 18-let´ y. Jeho jednoduch´ y d˚ ukaz Bertrandova postul´ atu, ˇze mezi kaˇzd´ ym pˇrirozen´ ym ˇc´ıslem a jeho dvojn´asobkem ˇ leˇz´ı prvoˇc´ıslo, zdaleka pˇredˇcil p˚ uvodn´ı Cebyˇ sev˚ uv d˚ ukaz z roku 1850. Erd˝os˚ uv u ´spˇech se dostal do povˇedom´ı anglicky mluv´ıc´ıch matematik˚ u ve formˇe verˇs´ıku od Nathana Finea: “Chebyshev said it, and I say it again There is always a prime between n and 2n.”
2
Matka
Paula spojovalo s matkou velmi siln´e pouto. Paulovy dvˇe sestry totiˇz zemˇrely na sp´ alu, kdyˇz byla matka s mal´ ym Paulem v porodnici. Matka se ze ztr´aty nikdy nevzpamatovala a o Paula se vˇzdy pˇrehnanˇe b´ala. Nen´ı divu, ˇze byl Paul nesamostatn´ y. Traduje se, ˇze si aˇz do 11 let neumˇel zav´azat tkaniˇcky a ˇze si poprv´e namazal chleba m´ aslem v Anglii na sv´ ych doktorsk´ ych studi´ıch. Po uvolnˇen´ı ˇzelezn´e opony od roku 1964 jej matka (tehdy 84-let´a) doprov´azela na cest´ ach, a to aˇz do sv´e smrti v roce 1971. Jedli spolu, Paul ji drˇzel za ruku, kdyˇz us´ınala, a z jej´ı smrti se jen pomalu vzpamatov´aval. Jeˇstˇe 5 let po smrti matky se odehr´ ala sc´ena, kdy se pˇr´ıtel Paula pt´a, jak se m´a, a Paul ˇr´ık´a, ˇze se c´ıt´ı smutn´ y, protoˇze mu zemˇrela matka... Matka byla tak´e ˇz´ arliv´ a, kdykoliv se Paul vyskytoval v bl´ızkosti nˇejak´e ˇzeny. Nemˇela ale d˚ uvod, protoˇze Paulovi podle jeho slov fyzick´ a rozkoˇs p˚ usobila bolest, a tak se nikdy neoˇzenil ani nemˇel ˇz´adn´ y v´aˇzn´ y vztah.
Matka i otec byli stˇredoˇskolsk´ ymi profesory matematiky a mohli do jej´ıch taj˚ u mal´eho Paula zasvˇecovat. Otec jej tak´e nauˇcil francouzsky a anglicky, ale jelikoˇz mˇel znalosti pouze teoretick´e, z˚ ustal Paulovi po cel´ y ˇzivot siln´ y pˇr´ızvuk.
3
Anonymous Group
ˇ st´ı matematici se sch´ Madarˇ azeli ve 30. letech pravidelnˇe v budapeˇsˇtsk´em parku u sochy Anonyma, kronik´ aˇre 12. stolet´ı, zaˇcalo se jim proto pˇrezd´ıvat “Anonymous Group”. Bavili se hlavnˇe o matematice, ale tu a tam sklouzla ˇreˇc i na politiku, ˇ coˇz bylo ve faˇsizuj´ıc´ım se Madarsku s antisemitsky zaloˇzen´ ym M. Horthym v ˇcele
2
nebezpeˇcn´e (vˇsichni ˇclenov´e skupiny byli totiˇz ˇzidovsk´eho p˚ uvodu). Tehdy vytvoˇril Paul sv˚ uj speci´ aln´ı jazyk - “erd˝ oˇstinu” - kter´ y se ujal v matematick´ ych kruz´ıch po cel´em svˇetˇe. Komunist´e byli people on the long wavelength, protoˇze ˇcerven´e svˇetlo m´ a dlouhou vlnovou d´elku. Tak´e mˇel speci´aln´ı term´ın pro dˇeti a vˇse mal´e epsilon, pro ˇzeny bosses a pro muˇze slaves, pro hudbu noise a pro alkohol poison. Give me an epsilon of poison byla ˇz´ adost o kapku v´ına. A na ot´azku, kdy se chlapec st´ av´ a muˇzem, odpov´ıdal: An epsilon becomes a slave when he starts running after bosses. Je jasn´e, ˇze v prostˇred´ı, kde na jeho origin´aln´ı slovn´ık nebyli zvykl´ı, se dostal nejednou do pot´ıˇz´ı. V tomto obdob´ı se stala ˇclenkou skupiny nadan´a Esther Kleinov´a a pˇriˇsla s n´asleduj´ıc´ı ´ u ´lohou a rovnou i jej´ım elegantn´ım ˇreˇsen´ım. Uloha 1: “Kolik bod˚ u, z nichˇz ˇz´ adn´e 3 neleˇz´ı v pˇr´ımce, je potˇreba zadat, aby nˇekter´e 4 z nich tvoˇrily vrcholy konvexn´ıho ˇctyˇru ´heln´ıku?” 2 Probl´em krouˇzek matematik˚ u zaujal, zobecnili jej a zanedlouho vyrukovali s hypot´ezou, ˇze 2n−2 + 1 bod˚ u vˇzdy staˇc´ı, abychom mezi nimi naˇsli vrcholy konvexn´ıho n-´ uheln´ıku. Dosud nen´ı hypot´eza dok´az´ana, ale hned po nˇekolika t´ ydnech naˇsel Gy˝orgy Szekeres poˇcet bod˚ u (samozˇrejmˇe vˇetˇs´ı neˇz 2n−2 + 1) postaˇcuj´ıc´ı pro existenci konvexn´ıho n-´ uheln´ıku. T´ım si z´ıskal ruku Esther a d´ıky tomu P. Erd˝ os nazval u ´lohu Happy-End Problem a tak tak´e vstoupila do povˇedom´ı matematik˚ u. Gy˝ orgy mˇel ˇstˇest´ı, ˇze Paul nemˇel z´ajem o ˇzeny, jinak by mu asi Esther musela d´ at koˇsem, protoˇze P. Erd˝os vz´apˇet´ı podstatnˇe Szekeresovu ˇ o prvn´ı Erd˝os˚ postaˇcuj´ıc´ı podm´ınku vylepˇsil. Slo uv v´ ysledek z Ramseyovy teorie oblasti matematiky, jej´ımˇz byl pr˚ ukopn´ıkem a jiˇz obohatil nesˇcetn´ ymi v´ ysledky.
4
Na cest´ ach
Rok po vyˇreˇsen´ı probl´emu s happy-endem odj´ıˇzd´ı P. Erd˝os na post-dock´ y stipendijn´ı pobyt do Anglie (je mu teprve 21 let - vysokoˇskolsk´a a doktorsk´a studia absolvoval ˇ z´ aroveˇ n!). Antisemitsk´e Madarsko pro nˇej nen´ı bezpeˇcn´e. Podle slov B´ely Bol3 lob´ ase : “Od roku 1934 sp´ı Erd˝os jen v´ yjimeˇcnˇe 7 dn´ı ve stejn´e posteli.” D´a se ˇr´ıci, ˇze P. Erd˝ os zasvˇetil matematice ˇzivot: nemˇel ˇzenu ani dˇeti a ˇr´ık´aval, ˇze majetek je na obt´ıˇz (cestoval s otrhan´ ym kufrem naplnˇen´ ym sotva z tˇretiny a oranˇzovou ˇaku Centrum Aruh´ ´ igelitkou budapeˇsˇtsk´eho obchod´ az). Vyslouˇzil si t´ım pˇrezd´ıvku “matematick´ y mnich”. Erd˝ osov´ ym stylem pr´ ace bylo zaklepat na dveˇre (ˇcasto bez pˇredchoz´ıho ohl´aˇsen´ı), prohl´ asit my brain is open a vrhnout se s dan´ ym matematikem do intenzivn´ı pr´ace. Po nˇekolika dnech se pak odebral d´al se slovy another roof, another proof. Kv˚ uli sv´e naprost´e nesamostatnosti nebyl snadn´ ym hostem a manˇzelky matematik˚ u b´ yvaly zpravidla po tˇech nˇekolika dnech peˇcov´an´ı o Paula tot´alnˇe vyˇcerpan´e. Stejnˇe tak b´ yvali vyˇcerpan´ı i jeho kolegov´e, protoˇze P. Erd˝os pˇr´ıliˇs mnoho nespal, ˇcasnˇe r´ano uˇz sv´eho hostitele budil nesnesiteln´ ym r´amusem v kuchyni ˇci koupelnˇe a ohlaˇsoval t´ım n´ astup k dalˇs´ı intenzivn´ı pr´ aci. Dennˇe tak´e P. Erd˝os volal mnoha zn´am´ ym matematik˚ um a ˇreˇsil s nimi matematick´e probl´emy po telefonu. Nikdy se nestaral o to, kolik je pr´ avˇe na druh´em konci svˇeta hodin. S oblibou tvrdil I am reality. A psal dopisy, pr˚ umˇernˇe 4 aˇz 5 dennˇe. Typick´ y zaˇc´atek dopisu vid´ıme na obr´azku. Na cest´ ach mu u ´tˇechu pˇrin´ aˇs´ı intenzivn´ı pr´ace. V Anglii se vˇenuje i nad´ale Ramseyovˇe teorii, kter´ a - zjednoduˇsenˇe ˇreˇceno - hled´a minim´aln´ı poˇcet prvk˚ u, jeˇz ´ zaruˇcuj´ı nˇejakou vlastnost. Klasick´ ym pˇr´ıkladem je Party Problem. Uloha 2:“Jak´ y 2 Konvexn´ ı je takov´ yu ´tvar, kter´ y s libovoln´ ymi dvˇ ema body obsahuje i u ´ seˇ cku, kter´ a je spojuje. Napˇr. u ´ seˇ cka, pˇr´ımka, kruh, troj´ uheln´ık jsou konvexn´ı u ´tvary v rovinˇ e. 3 B´ ˇ ˇ ela Bollob´ as je madarsk´ y matematik, kter´ y byl v´ıtˇ ezem vˇsech madarsk´ ych matematick´ ych soutˇ eˇ z´ı od sv´ ych 14 let. V 17 letech napsal prvn´ı spoleˇ cn´ y ˇ cl´ anek s Erd˝ osem. Dnes se vˇ enuje extrem´ aln´ı teorii graf˚ u a n´ ahodn´ ym graf˚ um.
3
je nejmenˇs´ı moˇzn´ y poˇcet host˚ u na narozeninov´e oslavˇe, m´a-li b´ yt zajiˇstˇeno, ˇze mezi nimi existuje trojice, kde kaˇzd´ y zn´a kaˇzd´eho, nebo existuje trojice, kde nikdo nezn´a ˇ je 6 osob.” Pokud poˇzadujeme stejnou vlastnikoho? Ukaˇzte, ˇze spr´ avn´ a odpovˇed nost po ˇctveˇric´ıch, pak je minim´aln´ı poˇcet lid´ı 18. Pro pˇetice uˇz se pouze v´ı, ˇze minim´ aln´ı poˇcet host˚ u je nˇekde mezi 43 a 49 a pro ˇsestice mezi 102 a 165. Zobecnˇen´ı probl´emu vedlo k zaveden´ı Ramseyov´ ych ˇc´ısel, jejichˇz vlastnosti P. Erd˝os s oblibou ˇablovi, kter´ studoval. Tak´e r´ ad vypr´ avˇel historku o d´ y se n´as m˚ uˇze zeptat na cokoliv, ˇabel zept´a na minim´aln´ı a pokud neodpov´ıme spr´ avnˇe, zniˇc´ı lidstvo. Jestliˇze se n´as d´ poˇcet host˚ u pro zajiˇstˇen´ı pˇetice, kde kaˇzd´ y zn´a kaˇzd´eho, nebo nikdo nikoho, rad´ı P. Erd˝ os, aby se vˇsichni matematici spojili a pokusili se otestovat hrubou silou ˇabel na minim´aln´ı poˇcet host˚ vˇsechny moˇznosti. Zept´ a-li se ale d´ u pro ˇsestice, je ˇ lepˇs´ı zkusit zlikvidovat d´ abla, neˇz nˇeco poˇc´ıtat. V roce 1938 se P. Erd˝ os pˇresouv´a do americk´eho Princetonu, zn´am´eho r´aje vˇedc˚ u, kde jsou odˇr´ıznuti od v´ alky a nemaj´ı ˇz´adn´e uˇcebn´ı povinnosti. Setk´av´a se ˇ adn´ tu s Albertem Einsteinem, Kurtem G¨odelem a Johnym von Neumannem. 4 Z´ y z tˇechto tˇr´ı vˇedc˚ u ale nem´ a Erd˝ osovo ˇc´ıslo 1! V roce 1948 se P. Erd˝ os po letech poprv´e vrac´ı do Budapeˇsti a s radost´ı zjiˇsˇtuje, ˇze jeho matka i bl´ızk´ y pˇr´ıtel Paul Tur´an pˇreˇzili v´alku. Ale ˇrada jeho pˇr´atel a pˇr´ıbuzn´ ych ˇ takov´e ˇstˇest´ı nemˇela. V Madarsku z˚ ust´av´a pouh´e 3 mˇes´ıce. Od roku 1949 je ˇ Madarsko pod vlivem J. V. Stalina a P. Erd˝os opˇet pendluje mezi USA a Velkou Brit´ ani´ı a tak´e konferencemi po cel´em svˇetˇe. Jeho cestov´an´ı se neobejde bez probl´em˚ u se Samem (tak pˇrekˇrtil USA podle uncle Sam) a Joem (podle Josipa Stalina). Je tˇreba dodat, ˇze do nejr˚ uznˇejˇs´ıch probl´em˚ u dost´av´a P. Erd˝ose hlavnˇe jeho upˇr´ımnost. U jednoho americk´eho pohovoru tˇreba ˇrekl, ˇze Marx jistˇe nebyl hlup´ak. Podle P. Erd˝ ose nen´ı ˇz´ adn´ a zemˇe na svˇetˇe bez viny, a tak odm´ıt´a nab´ızen´a ˇ obˇcanstv´ı a prohlaˇsuje sama sebe za svˇetoobˇcana. Na pˇr´ımluvu madarsk´ ych pˇr´atel ˇ dost´ av´ a v 50. letech speci´ aln´ı pas, kter´ y mu umoˇzn ˇuje vstoupit do Madarska, ˇ kdykoliv chce. St´ av´ a se ˇclenem madarsk´e Akademie vˇed a nov´e ˇcleny v´ıt´a s osobit´ ym sarkasmem: Jsem r´ ad, ˇze jste se stal polobohem.
5
Kniha
V roce 1940 pˇrejmenoval P. Erd˝ os Boha na SF (Supreme Fascist) a tak´e NOGUT (Number-One Guy Up There). B˚ uh totiˇz v jeho oˇc´ıch nen´ı dobrotiv´ y, kdyˇz dopouˇst´ı na Zemi takov´e utrpen´ı a nespravedlnost. SF m˚ uˇze za vˇse ˇspatn´e: Kdyˇz Paul nem˚ uˇze tˇreba nˇeco naj´ıt, jistˇe mu to schoval SF. Erd˝osovo kr´edo zn´ı: Kaˇzd´y se m´ a 4 Johny von Neumann je povaˇ ˇ zov´ an za otce informatiky. Byl tak´ e madarsk´ eho p˚ uvodu, ale byl prav´ ym opakem P. Erd˝ ose, miloval ˇ zeny, rychl´ a auta, mexick´ e j´ıdlo a byl na kaˇ zd´ em veˇ c´ırku nejz´ abavnˇ ejˇs´ım spoleˇ cn´ıkem.
4
chovat tak, aby drˇzel sv´e SF sk´ ore n´ızko. A jak se SF sk´ ore poˇc´ıt´ a? Udˇel´ ate-li nˇeco ˇspatn´eho, SF m´ a plus 2 body, neudˇel´ ate-li nˇeco dobr´eho, co jste udˇelat mohli, SF m´ a plus 1 bod. On s´ am jde ostatn´ım pˇr´ıkladem, m´a r´ad dˇeti a pom´ah´a nemocn´ ym, jakmile slyˇs´ı o nˇejak´e charitativn´ı sb´ırce, hned bez v´ah´an´ı pˇrisp´ıv´a. A ˇcasto vyhled´av´a a podporuje mlad´e nadan´e matematiky. Nejmladˇs´ım Erd˝ osov´ ym spoluautorem byl 14-let´ y L´ajos P´osa. P. Erd˝os si jej vyzkouˇsel hned pˇri prvn´ım setk´ an´ı n´asleduj´ıc´ı u ´lohou (pokud ji do 10 minut vyˇreˇs´ıte, ´ P. Erd˝ os by v´ as pˇribral do sv´eho t´ ymu). Uloha 3: “Proˇc mezi prvn´ımi pˇrirozen´ ymi 2n ˇc´ısly, kdyˇz libovolnˇe vybereme n + 1 z nich, budou mezi vybran´ ymi aspoˇ n dvˇe nesoudˇeln´ a?” 5 Nˇekter´e ze z´ azraˇcn´ ych dˇet´ı, napˇr. L. P´osa, matematicky zemˇreli (erd˝ oˇstina), mnoh´e se ale staly matematickou elitou, napˇr. B. Bollob´as. Kromˇe vyhled´ av´ an´ı z´ azraˇcn´ ych dˇet´ı mˇel P. Erd˝os z´alibu ve vypisov´an´ı odmˇen za vyˇreˇsen´ı otevˇren´ ych matematick´ ych probl´em˚ u. Odmˇeny byly ˇcasto dost vysok´e a nˇekter´e probl´emy z˚ ustaly nevyˇreˇsen´e dodnes a odmˇenu za nˇe lze st´ale z´ıskat! Podle P. Erd˝ ose m´ a SF transfinitn´ı knihu (transfinitn´ı vyjadˇruje obrovitost t´eto knihy a pˇr´ıvlastek si P. Erd˝ os vyp˚ ujˇcil od sv´eho obl´ıbence G. Cantora), kter´a obsahuje vˇsechna matematick´ a tvrzen´ı a jejich nejhezˇc´ı d˚ ukazy. Dobˇr´ı matematici jsou ti, jejichˇz d˚ ukazy se podobaj´ı tˇem z knihy, a nejvˇetˇs´ı pochvala od P. Erd˝ose zn´ı: Your proof is straight from the Book. Jakou z´avaˇznost P. Erd˝os knize pˇrikl´ad´a, je c´ıtit z jeho slov: You don’t have to believe in God, but you should believe in the Book. Zat´ımco velk´ a ˇc´ ast matematik˚ u spad´a do kategorie “budovatel´e teori´ı”, P. Erd˝os patˇril do kategorie “ˇreˇsitel´e probl´em˚ u”. Rozd´ıl mezi A. Einsteinem a P. Erd˝osem je n´ asleduj´ıc´ı: “Einstein mˇel ve fyzice nos na centr´aln´ı t´emata a nepodl´ehal ˇz´adn´ ym jin´ ym probl´em˚ um, zat´ımco Erd˝ os podlehl s radost´ı kaˇzd´emu zaj´ımav´emu probl´emu a mnoh´e z nich podlehly Erd˝ osovi.” P. Erd˝ os miloval pˇrirozen´ a ˇc´ısla a rozumˇel jim jako nikdo jin´ y. Zat´ımco vˇetˇsina matematik˚ u u teorie ˇc´ısel zaˇc´ın´ a a pozdˇeji se pˇresouv´a do jin´ ych oblast´ı, P. Erd˝os z˚ ustal teorii ˇc´ısel vˇern´ y cel´ y ˇzivot. Tak´e miloval teorii graf˚ u, je tv˚ urcem teorie n´ ahodn´ ych graf˚ u a extrem´ aln´ı teorie graf˚ u. Jeho pravdˇepodobnostn´ı metoda dokazov´ an´ı se dnes hojnˇe vyuˇz´ıv´ a v teoretick´e informatice. Ramseyova teorie spojuje ˇ P. Erd˝ ose s Ceskoslovenskem, protoˇze celou ˇradu ˇcl´ank˚ u z t´eto discipl´ıny napsal spolu s Vojtˇechem R¨ odlem a Jaroslavem Neˇsetˇrilem. Byl ale schopen vyˇreˇsit i u ´lohy ze vzd´ alen´ ych oblast´ı matematiky. Staˇcilo, aby mu matematici dodali z´akladn´ı definice a dobˇre zformulovali probl´em, a po kr´atk´e dobˇe P. Erd˝os pˇriˇsel s ˇreˇsen´ım.
6
St´ aˇ r´ı
Slavn´ y matematik G. H. Hardy tvrdil, ˇze matematika je hrou mlad´ ych muˇz˚ u: “Galois zemˇrel ve 21 letech, Abel ve 27, Riemann ve 40. . . Nezn´am pˇr´ıpad, kdy by nˇejak´ y v´ yznamn´ y v´ ysledek dok´ azal matematik starˇs´ı 50 let.” P. Erd˝os se s G. H. Hardym setkal hned pˇri sv´em prvn´ım pobytu v Anglii. Tehdy jeˇstˇe nevˇedˇel, ˇze bude nejlepˇs´ım protipˇr´ıkladem k Hardyho domnˇence. Poznamenejme ovˇsem, ˇze pracovat 19 hodin dennˇe, coˇz bylo Erd˝ osovo tempo po smrti matky, tedy 25 posledn´ıch let ˇzivota, mu z velk´e ˇc´ asti umoˇzn ˇovala k´ava a amfetaminy. S oblibou citoval v´ yrok sv´eho kolegy a pˇr´ıtele Alfr´eda R´enyiho: “Matematik je stroj, kter´ y vyr´ab´ı z kafe teor´emy.” Dalˇs´ı z Paulov´ ych pˇr´ atel-matematik˚ u, Paul Tur´an, po vypit´ı k´avy v USA pr´ y vyslovil: “Slab´e kafe je dobr´e jen na lemmata.” 6 Na rady pˇr´atel, aby zvolnil sv´e pracovn´ı tempo, P. Erd˝ os odpov´ıdal: Na odpoˇcinek je ˇcas v hrobˇe. A stejnˇe bˇritce popsal zn´ amky muˇzsk´e senility: Nejprve muˇz zapom´ın´ a sv´e teor´emy, pot´e si 5 Dvˇ e
pˇrirozen´ aˇ c´ısla jsou nesoudˇ eln´ a, pokud nemaj´ı ˇ z´ adn´ eho pˇrirozen´ eho dˇ elitele vˇ etˇs´ıho neˇ z 1. je m´ enˇ e d˚ uleˇ zit´ e matematick´ e tvrzen´ı. Vˇ etˇsinou hraje pomocnou roli pˇri d˚ ukazu matematick´ e vˇ ety, slouˇ z´ı k zpˇrehlednˇ en´ı d˚ ukazu. 6 Lemma
5
zapom´ın´ a zapnout poklopec a nakonec si zapom´ın´ a poklopec rozepnout. Senilita ale Paula Erd˝ ose nepostihla, p´ alilo mu to aˇz do smrti a zemˇrel na matematick´e konferenci. A abychom nekonˇcili v ponur´em duchu, zanechal n´am P. Erd˝os s ironi´ı sobˇe vlastn´ı epitaf s n´ apisem: Koneˇcnˇe uˇz nehloupnu.
ˇ sen´ı u Reˇ ´ loh ´ • Uloha 1:“Kolik bod˚ u, z nichˇz ˇz´adn´e 3 neleˇz´ı v pˇr´ımce, je potˇreba zadat, aby nˇekter´e 4 z nich tvoˇrily vrcholy konvexn´ıho ˇctyˇru ´heln´ıku?” Je snadn´e si rozmyslet, ˇze 4 body nestaˇc´ı (mohou vytvoˇrit vrcholy ‘vykousnut´eho’ ˇctyˇru ´heln´ıka). Esther Kleinov´a elegantnˇe dok´azala, ˇze 5 bod˚ u jiˇz staˇc´ı. Mohou totiˇz nastat pouze 3 situace, viz obr´azek:
1. 1 z bod˚ u leˇz´ı uvnitˇr konvexn´ıho obalu ostatn´ıch. 7 Pak je tento konvexn´ı obal hledan´ ym konvexn´ım ˇctyˇru ´heln´ıkem. 2. Konvexn´ı obal vˇsech 5 bod˚ u tvoˇr´ı konvexn´ı pˇeti´ uheln´ık (tedy ˇz´adn´ y z bod˚ u neleˇz´ı uvnitˇr konvexn´ıho obalu ostatn´ıch). Pak libovoln´e 4 z nich tvoˇr´ı vrcholy hledan´eho konvexn´ıho ˇctyˇru ´heln´ıka. 3. 2 z bod˚ u leˇz´ı uvnitˇr konvexn´ıho obalu ostatn´ıch. Spoj´ıme-li je pˇr´ımkou, pak na jedn´e stranˇe od n´ı budou leˇzet 2 body. Tyto 2 body spolu s 2 body na pˇr´ımce jsou vrcholy hledan´eho konvexn´ıho ˇctyˇru ´heln´ıka. ´ • Uloha 2:“Jak´ y je nejmenˇs´ı moˇzn´ y poˇcet host˚ u na narozeninov´e oslavˇe, m´ali b´ yt zajiˇstˇeno, ˇze mezi nimi existuje trojice, kde kaˇzd´ y zn´a kaˇzd´eho, nebo ˇ je 6 existuje trojice, kde nikdo nezn´a nikoho? Ukaˇzte, ˇze spr´avn´a odpovˇed osob.” Snadno si rozmysl´ıme, ˇze 5 host˚ u nestaˇc´ı. Uvaˇzujme oslavu se 6 hosty a ty si pˇredstavme jako body. Pokud se znali jiˇz pˇred oslavou, spoj´ıme je u ´seˇckou. Pokud se na oslavˇe vid´ı prvnˇe, nespoj´ıme je. (Definovali jsme vlastnˇe graf.) ˇ spojen s aspoˇ Vyberme libovoln´ y bod. Jistˇe je bud n 3 ostatn´ımi, nebo nen´ı spojen s aspoˇ n 3 ostatn´ımi. Pˇredpokl´adejme, ˇze nastal prvn´ı pˇr´ıpad (druh´ y by se oˇsetˇril analogicky). Uvaˇzujme tedy ˇctveˇrici bod˚ u, kde n´aˇs vybran´ y bod ˇ nˇekter´a dvojice ze zbyl´ je spojen se vˇsemi ostatn´ımi. Pak bud ych 3 bod˚ u je spojena u ´seˇckou a spolu s vybran´ ym bodem tvoˇr´ı hledanou trojici host˚ u, kde kaˇzd´ y znal kaˇzd´eho jiˇz pˇred oslavou. Nebo ˇz´adn´a dvojice ze zbyl´ ych 3 bod˚ u nen´ı spojena u ´seˇckou a my jsme tedy naˇsli 3 hosty, kteˇr´ı se vid´ı prvnˇe. 7 Konvexn´ ı obal nˇ ejak´ eho koneˇ cn´ eho poˇ ctu bod˚ u je nejmenˇs´ı konvexn´ı u ´tvar obsahuj´ıc´ı dan´ e body.
6
´ • Uloha 3:“Proˇc mezi prvn´ımi pˇrirozen´ ymi 2n ˇc´ısly, kdyˇz libovolnˇe vybereme n + 1 z nich, budou mezi vybran´ ymi aspoˇ n dvˇe nesoudˇeln´a?” Mezi libovoln´ ymi n + 1 ˇc´ısly budou urˇcitˇe alespoˇ n dvˇe po sobˇe jdouc´ı a ta jsou nesoudˇeln´ a.
References [1] Csicsery G.-P.: N Is a Number: A Portrait of Paul Erd˝os. DVD, Springer, Berlin, 1999. [2] Hoffman P. : The Man Who Loved Only Numbers. The Story of Paul Erd˝os and the Search for Mathematical Truth. Hyperion, New York, 1998. [3] Schechter B.: My brain is open: The mathematical journeys of Paul Erd˝os. Simon & Schuster, New York, 2000. [4] Wikipedia (The free encyclopedia): Paul Erd˝os [online]. Posledn´ı revize 2. ˇcervna 2010 [cit. 5. 6. 2010] http://en.wikipedia.org/wiki/Paul Erd˝os [5] The Erd˝ os Number Project [online]. Posledn´ı revize 30. dubna 2010 [cit. 5. 6. 2010] http://www.oakland.edu/enp/
Ing. L’ubom´ıra Balkov´ a, Ph.D. ˇ Katedra matematiky FJFI CVUT v Praze Trojanova 13, Praha 2 120 00
[email protected]
7
