barvu (sousedství „přes roh“ se nepočítá).Matematikům trvalo téměř 150 let, než objevili zdů-
vod nění, které je správné a obecně uznávané. Jeden z autorů tohoto důkazu, Robin Thomas,
je bývalý student naší fakulty. Najdete zdůvodnění pro lehčí verzi s pěti (šesti, …) barvami?
Příběh z vězení: Ve věznici ve městě N hraje ředitel se všemi svými 100 vězni tuto krutou
hru. Do 100 skříněk v pracovně umístil jejich jména, jedno v každé skříňce, a postupně si
k sobě vězně povolává. Každý smí nahlédnout do některých 50 skříněk, pak jsou uzav -
řeny a vězeň musí opustit ředitelovu pracovnu a s ostatními se nemůže domlouvat. Pokud
každý z vězňů v některé z otevřených skříněk najde své jméno, budou všichni propuštěni
na svobodu. Pokud byť i jeden z nich selže a v padesáti otevřených skříňkách své jmé no
nenalezne, budou všichni vězňové popraveni. Mohou si vězňové předem domluvit vhodný
postup, který jim dá alespoň nějakou šanci na přežití?
Vězeň A: „Každý otevřeme prvních 50 skříněk, je to všechno jedno.“
Vězeň B: „Pak nás jistě všechny popraví!“
Vězeň C: „Každý otevřeme nějakých 50 skříněk, třeba náhodně. S 50% šancí nalezneme
své jméno. Celkem máme šanci na přežití (1/2) krát (1/2) krát … krát (1/2) (100 krát), neboť
vzájemně nezávislé šance se násobí. Vychází to zhruba nula celá nula, třicet nul, sedmička
a nějaké drobné. Ne mnoho, ale lepší než nic …“
Vězeň D: „Znám postup, který nám všem zajistí více než 30% šance na přežití. Není to
100%, to ani nelze, ale stále lepší než nula celá nula nic. Budeme postupovat takto … “
Zkuste se zamyslet nad několika otázkami a zodpovědět je. Nejprve lehčí. Proč návrh
Vězně A dává nulovou šanci přežití? Proč Vězeň C šance mezi sebou násobil? Věřili byste
Vězni D, kdyby sliboval postup se 70% šancí na přežití? A teď ta nejtěžší a nejzajímavější –
jaký postup tedy dává 30% šanci na přežití?
Některé z uvedených hádanek jsou lehčí, jiné těžší až velmi těžké. Řešení lze nalézt na webu
http://kam.mff.cuni.cz/resenihadanek
Kombinatorika a teorie grafů zkoumá struktury, které modelují vztahy mezi konečným
počtem objektů (třeba silnice mezi městy). Má četné aplikace – hledání nejkratší cesty
(navigace, hledání v jízdních řádech), rozvrhování (předmětů ve škole, nebo realizaci
proměnných v programu registry počítače), analýza chování datových struktur (četnost
přístupů do paměti, očekávaná časová složitost), a další.
Kombinatorika a teorie
grafů patří mezi disciplíny,
ke kterým stačí papír
a tužka, proto můžeme
pořádat přednášky i na
neob vyklých místech.
Náš student Jan Hladký
přednáší na Jarní škole
ve Vysoké Lípě.
Informati ka: Kombinatorika a teorie grafů
77