Student World

Matematický klub byl sice jen jakýmsi neformálním sdružením přátel a kolegů s podobnými zájmy, přesto ale měly často přednášky velmi vysokou akademickou úroveň. Ken Keeler, který svůj referát nazval „Druhotné dělení čtverců“, je jedním z matematicky nejnadanějších spisovatelů v týmu Simpsonových.

Absolvoval Harvard s nejvyšším možným vyznamenáním (summa cum laude), což znamená, že mezi aplikovanými matematiky, kteří dokončili bakalářský stupeň v roce 1983, patřil k absolutní špičce. Potom se přesunul na Stanfordovu univerzitu, kde vystudoval na magisterské úrovni elektroinženýrství, aby se odtud vrátil zpět na Harvard, kde získal doktorát v oboru aplikované matematiky. Jeho doktorská práce nesla kryptický název „Optimální kódování segmentace obrazu a jeho reprezentace pomocí zobrazení“. Keeler potom získal místo v Bellových laboratořích firmy AT&T v New Jersey, což je zařízení, jehož výzkumníci se honosí sedmi Nobelovými cenami. V této době se Keeler potkal s Jeffem Westbrookem. Oba pracovali ve stejné oblasti výzkumu a společně napsali článek pod názvem „Krátké kódování rovinných grafů a zobrazení“. Napsali společně také scénář k televiznímu sci-fi seriálu StarTrek: Hluboký vesmír devět, ve kterém vystupují dva pódioví komici, kterým se podaří urazit skoro každého mimozemšťana v publiku, až kvůli nim vypukne válka.

Matematický klub se postupně rozrůstal. Občas se ani všichni zájemci o přednášku nevešli do místnosti, a bylo tedy třeba přesunout seanci ven a místo promítacího plátna použít zavěšených prostěradel. Nejpočetnější publikum, čítající až sto lidí, se scházelo zejména v případech, kdy přednášel nějaký hodně slavný matematik, jako tomu bylo kupříkladu v případě dr. Ronalda Grahama, vedoucího vědeckého pracovníka z Kalifornského ústavu telekomunikací a informačních technologií (California Institute for Telecomunications and Information Technology – (Cal(IT)). Mimochodem, Graham také proslul tím, že publikoval více než dva tucty článků spolu s Paulem Erdősem a patřil k předním popularizátorům koncepce Erdősových čísel. Kromě toho se Graham proslavil i takzvaným Grahamovým číslem, které v roce 1977 drželo rekord jako největší číslo, jaké kdy bylo užito v matematickém článku. Abychom si udělali o velikosti tohoto čísla představu, připomeňme nejprve pojem Planckova objemu, což je nejmenší jednotka objemu užívaná ve fyzice. Do atomu vodíku se jich vejde 10 na 73. Kdybychom vepsali každou cifru Grahamova čísla do jedné jednotky Planckova objemu, stále by se ještě takto zapsané Grahamovo číslo nevešlo do našeho vesmíru. Možná někomu pomůže informace, že číslo končí ciframi …2464195387.

Jednu z nejpamátnějších přednášek Matematického klubu měl na svědomí David S. Cohen, tvůrce velké věty Homerovy. Cohenova přednáška měla zvláštní význam, protože v ní hovořil o výzkumu, jímž se zabýval předtím, než se stal scenáristou televizních komedií. Po absolvování Harvardu strávil Cohen jeden rok v harvardské laboratoři robotiky a později se přesunul do Berkeley, kde získal magisterský diplom na Kalifornské univerzitě. V Berkeley se Cohen zaměřil na takzvaný pancake sorting problem (problém třídění palačinek), a právě tomuto tématu byla věnována jeho přednáška v Matematickém klubu.
Problém zformuloval v roce 1975 Jacob E. Goodman, který pracoval v oboru geometrie na City College of New York, a to pod pseudonymem Harry Dweighter (což se čte stejně jako „harried waiter“ – „uštvaný číšník“). Napsal k tomu toto:

Náš kuchař je poněkud nepořádný a jeho palačinky mají obvykle nestejné rozměry. Proto já, když potom nesu palačinky hostovi, je vždy cestou ke stolu přeskupím tak, aby byly seřazeny podle velikosti (největší dole, nejmenší nahoře). Dělám to tak, že jich vždy několik shora podeberu a tuto hromádku překlopím. Této operaci říkám „palačinkový přemet“ a opakuji ji tolikrát, kolikrát je třeba (přičemž se samozřejmě počet překlápěných palačinek může měnit při každém dalším přemetu). Nesu-li n palačinek, jaký je největší počet nezbytných palačinkových přemetů (jakožto funkce proměnné n), s nímž se mohu kdy setkat?

Jinými slovy, když Homer zajde do springfieldské městské palačinkárny, jak je tomu například v epizodě „Pokřivený svět Marge Simpsonové“ z roku 1997, a číšník mu přinese n palačinek náhodné velikosti, kolik přemetů bude v nejhorším možném případě třeba k tomu, aby se palačinky přeskupily do kýženého uspořádání podle velikosti? Tento největší možný nezbytný počet přemetů je znám pod názvem „palačinkové číslo“ („pancake number“) a označuje se symbolem Pn. Úkolem je nalézt vzorec pro výpočet této hodnoty v závislosti na počtu palačinek n.

Problém okamžitě zaujal matematiky, a to ze dvou důvodů. Zaprvé se zdá, že otázka souvisí s problémy teoretické informatiky, neboť přeskupování palačinek má svou obdobu v přeskupování dat. Druhým důvodem je fakt, že jde (možná překvapivě) o pekelně těžkou otázku, a matematici milují problémy, které je téměř nemožné vyřešit.
Problém lze trochu osvětlit na některých jednoduchých případech. Nejprve si položme otázku, jaké je palačinkové číslo pro pouhou jednu palačinku. Odpověď je 0, protože jedna palačinka nemůže být uspořádána nesprávně. Takže P1 = 0.
Dále spočtěme palačinkové číslo pro dvě palačinky. Dvojice palačinek buď přijde ve správném pořadí, nebo v nesprávném. Z těchto případů je snadné najít ten nejhorší, a ten vyžaduje právě jeden přemet. Takže P2 = 1.
A jak jsme na tom s třemi palačinkami? Tento případ už je o něco těžší, protože máme šest možností, jak mohou být palačinky na začátku uspořádány. V závislosti na původním pořadí se počet nezbytných přemetů pohybuje od nuly až po nejhorší případ, kdy je roven třem. Tudíž P3 = 3.

/obrázky, diagramy/

Obtížnost otázky roste s počtem palačinek, neboť přibývá možných počátečních uspořádání a také možných procedur převracení. Co je ovšem nejhorší, nezdá se, že by se z úvodní posloupnosti palačinkových čísel dalo vysledovat nějaké schéma nebo dokonce vzorec:

n 1 2 3 4 5 6 7 8 9 10
Pn 0 1 3 4 5 7 8 9 10 11

n 11 12 13 14 15 16 17 18 19 20
Pn 13 14 15 16 17 18 19 20 22 ?
/omluva za formátování, ale snad srozumitelné/

To, že ani nejvýkonnější počítače zatím nebyly schopny určit dvacáté palačinkové číslo, je způsobeno čistě jen obrovským počtem permutací a všech možných přemetových strategií, které je třeba posoudit. A ani po třech desetiletích nebyl zatím nikdo schopen obejít metodu hrubé síly s použitím výpočetní techniky a vymyslet nějaký chytrý předpis, který by palačinková čísla určil. Jediný pokrok, kterého zatím bylo dosaženo, spočívá v určení odhadů pro palačinková čísla shora i zdola. V roce 1979 se podařilo dokázat, že palačinkové číslo bude vždy menší než (5n + 5)/3. Odtud plyne, že můžeme vzít nějaký nesmyslně vysoký počet palačinek, řekněme tisíc, a můžeme bez obav říci, že i v nejhorším možném případě jejich původního uspořádání je budeme schopni přeskupit do kýženého pořadí za užití počtu přemetů, který bude menší než
(5 × 1 000 + 5)/3 = 1 668 1/3.

Protože třetinový přemet nedává smysl, můžeme uzavřít, že číslo P1000 je menší nebo nejvýše rovno 1 668. Tento výsledek se proslavil, protože se objevil v článku, který spolu napsali William H. Gates a Christos H. Papadimitrou. William H. Gates je známější pod jménem Bill Gates, spoluzakladatel Microsoftu, přičemž uvedený článek je považován za jedinou vědeckou práci, kterou kdy vydal.
Článek je založen na práci, kterou Gates vykonal jako student na Harvardu, a zmiňuje se ještě o jedné velmi pěkné variantě problému. Problém připálených palačinek se týká takových palačinek, které jsou na jedné straně připálené, a úkolem je podat je hostovi nejen správně seřazené podle velikosti, ale také správně orientované, tedy spálenou stranou dolů. Tento problém vynalezl právě David S. Cohen, když pracoval v Berkeley.

Cohen o problému připálených palačinek napsal jeden článek, v němž dokázal, že dolní a horní odhad pro nezbytný počet otočení pro připálené palačinky se pohybuje mezi 3n/2 a 2n – 2. Pokud zase jednou zkusíme případ tisíce palačinek, tentokrát ovšem připálených, zjistíme z Cohenova článku, že nejhorší možný scénář si může vynutit něco mezi 1 500 a 1 998 přemety.
To je to, co dělá tvůrce Simpsonových tak jedinečnými. Nejenže navštěvují Matematický klub, ale ještě jsou navíc schopni seriózně přednášet matematické referáty a dokonce jsou autory hlubokomyslných matematických pojednání.

Tento text je úryvkem z knihy
Simon Singh: Simpsonovi a jejich matematická tajemství
Argo a Dokořán 2015
O knize na stránkách vydavatele

autor