Projev předsedy Ústřední komise MO při slavnostním zahájení
ústředního kola 65. ročníku MO v Pardubicích
Dámy a pánové, vážení hosté, milí soutěžící,
mnohé malé děti v čase adventním méně zlobí doufajíce, že pod stromečkem
najdou vysněné dárky. K mým adventním nadějím v posledních
letech patří, že o vánočních prázdninách konečně vymyslím, o čem budu na
ústředním kole Matematické olympiády povídat. Stalo se tak naštěstí i tentokrát,
ještě před Novým rokem 2016. Nevím už, jakou souhrou myšlenek
jsem se dobral k poměrně triviálnímu zjištění, že jméno města, do kterého
jsme se dnes sjeli, je sestaveno z devíti různých písmen. Lze je proto využít
namísto číslic (od jedničky po devítku) pro hru jednoho hráče s tužkou a
papírem, hru, která je v současné době na celém světě snad nejoblíbenější.
P A R D U B I C E
D U B I C E P A R
I C E P A R D U B
A R P U B D C E I
U B D C E I A R P
C E I A R P U B D
R P A B D U E I C
B D U E I C R P A
E I C R P A B D U
Ano, vidíte příklad správně vyplněné tabulky při hře sudoku: v každém
z 9 řádků, 9 sloupců i devíti vyznačených bloků o 9 polích jsou všechna
písmena různá neboli v nich žádné z devíti písmen nikde nechybí. Je jasné,
že při hře sudoku vůbec nezáleží na tom, jakých 9 různých znaků do políček
tabulky 9 × 9 vpisujeme, mohou to být nejen číslice, ale i účelně vybraná
písmena.
Asi jste zpozorovali, že slovo Pardubice je k přečtení v prvním řádku
naší tabulky. Možná také někdo postřehl, že Pardubice přečteme i po řádcích
levého horního bloku a také že celá tabulka se vyznačuje jistou pravidelností,
Typeset by AMS-TEX
1
která zaručuje její „sudokost . Je založena na rozdělení písmen řádků do
tří trojic, které jsou v nové kopii tabulky barevně rozlišeny:
P A R D U B I C E
D U B I C E P A R
I C E P A R D U B
A R P U B D C E I
U B D C E I A R P
C E I A R P U B D
R P A B D U E I C
B D U E I C R P A
E I C R P A B D U
Že je celá tabulka v pořádku, je docela očividné, ty tři barvy to pěkně
zprůhledňují.
Uveďme teď ještě jednu tabulku sudoku, ve které jsou Pardubice k přečtení
ne dvakrát, ale dokonce třikrát.
P A R B D U C E I
D U B E I C A R P
I C E R P A U B D
C E I P A R B D U
A R P D U B E I C
U B D I C E R P A
B D U C E I P A R
E I C A R P D U B
R P A U B D I C E
Ano, jde o tři bloky na jedné úhlopříčce. Vlastně v celé tabulce jsou jen tři
2
různé bloky, spolu třikrát vedle sebe a třikrát pod sebou.
P A R B D U C E I
D U B E I C A R P
I C E R P A U B D
C E I P A R B D U
A R P D U B E I C
U B D I C E R P A
B D U C E I P A R
E I C A R P D U B
R P A U B D I C E
Že ony tři různé bloky nám vyhovují (sudokují) jak vedle sebe, tak pod
sebou, můžeme opět vysvětlit pomocí tří trojic písmen, které nově barevně
rozlišíme v prvních třech řádcích a prvních třech sloupcích:
P A R B D U C E I
D U B E I C A R P
I C E R P A U B D
C E I P A R B D U
A R P D U B E I C
U B D I C E R P A
B D U C E I P A R
E I C A R P D U B
R P A U B D I C E
Méně přehledné zaplnění má tabulka sudoku na další stránce. Není úplně
běžná, protože v ní chybí sedmičky, které jsou nahrazeny nulami. Jsou v ní
červeně vyznačena data, na která se budeme odvolávat v další části textu,
kterou věnujeme několika momentům jak z historie Pardubic, tak z historie
3
naší soutěže.
1 2 9 5 0 6 3 4 8
8 5 6 1 3 4 0 9 2
4 3 0 2 9 8 5 1 6
0 4 5 8 6 1 9 2 3
3 6 1 9 5 2 4 8 0
2 9 8 0 4 3 6 5 1
5 0 2 6 1 9 8 3 4
6 1 4 3 8 5 2 0 9
9 8 3. 4. 2 0 1 6 5
První dochovanou písemnou zprávou o Pardubicích je jedna papežská
listina z roku 1295. Je v ní zmíněn již existující pardubický klášter spolu
s dalšími kláštery cyriaků, jinak mnichů špitálského řádu křižovníků s červeným
srdcem.
Nejstarším dokladem o existenci Pardubic jako města je závěť z roku
1340, kterou sepsal rytíř Arnošt z Hostýně, zakladatel šlechtického rodu,
označovaného později jako páni z Pardubic. Ze čtyř synů Arnošta z Hostýně
se nejvíce proslavil ten nejstarší, stejnojmenný Arnošt, kterého známe z dějepisu
již pod jménem Arnošt z Pardubic. Stal se historicky prvním pražským
arcibiskupem a byl nejbližším rádcem a důvěrníkem císaře Karla IV.
Přeskočme však šest století od počátků Pardubic k počátkům naší soutěže.
První, tehdy československé finále matematické olympiády se konalo
v jednu červnovou neděli roku 1952. Účastníci z celé republiky se sjeli do
Prahy již v sobotu a navštívili večerní představení v tehdejším Komorním
divadle. Ve vlastní nedělní soutěži pak zvítězil žák Juraj Bosák z Bratislavy,
budoucí přední slovenský matematik, který aktivně pracoval zejména
v teorii grafů až do své náhlé smrti ve věku 54 let.
4
Zatímco v první dekádě naší soutěže se její finále konalo vždy v Praze,
v dalších ročnících se dějišti těchto ústředních kol stávala různá města naší
země, zejména krajská, ale i okresní, ba rovněž města i bez těchto správních
titulů krásná a významná, kupříkladu Jevíčko a Litomyšl z kraje Pardubického.
Do jeho sídla, krajského města Pardubic, se naše finále vrací po relativně
dlouhé době 33 let, tedy poprvé od roku 1983. Tehdejší účastníci již
čtyřdenní květnové akce si mohli kromě vlastního počítání také užít besedy
s účastníky mistrovství světa v ledním hokeji. Nevzpomněl jsem to jen tak
— lední hokej totiž patří, vedle perníku, ploché dráhy a koňských dostihů,
k městu Pardubice neodmyslitelně. A tak je v naší historické tabulce sudoku
chronologicky správně uveden rok 1923, ve kterém byl založen slavný
hokejový klub Dynamo Pardubice.
Od hokeje však zpět k matematické olympiádě, jejíž 65. ročník právě
vrcholí. Píše se, jak je upomenuto v posledním řádku tabulky, třetí duben
2016 a my v krásném prostředí pardubického zámku zahajujeme letošní
finále naší soutěže. Rád bych při této příležitosti všem přítomným představil
čtyři své kolegy, kteří dlouhá léta naplno pracovali a dosud pracují pro
matematickou olympiádu. Požádám tak zdvořile, aby se ke mně dostavili
pánové Jaroslav Švrček (autor stovek úloh, místopředseda od r. 2001), Dag
Hrubý z Jevíčka (3 finále 1993–1995, 23 soustředění od r. 1993), Karel Horák
(redaktor textů, tajemník od r. 1982) a Leo Boček (tajemník 1978–1987,
předseda 1988–2001). Myslím, že si pánové zasloužíte uznalý potlesk všech
přítomných. ( . . . ) Dovolte, milí kolegové, abych vám předal jako upomínku
na dnešní den malé, prozatím v krabičkách ukryté suvenýry, otevřete je však
prosím, až na to zřejmě přijde čas v průběhu mého dalšího povídání. ( . . . )
Děkuji, přátelé, můžete se laskavě vrátit na svá místa. ( . . . )
Úvodem další části svého vyprávění o tabulkách sudoku zdůrazním rozdíl
mezi oběma finálovými kategoriemi A a P naší olympiády. Soutěžící
programovací kategorie P, kterou tady v Pardubicích zahájíme v nejbližší
středu, řeší úlohy na sestavení algoritmů, tj. postupů k řešení určité úlohy,
jakou třeba může být vlastní hra sudoku. Ta však na programu kategorie
P určitě nebude, protože algoritmy pro sudoku jsou po řadu let dobře
známy, a různé počítačové programy, jak hrát sudoku, jsou k mání na internetu.
Naproti tomu soutěžící kategorie A budou již zítra a pozítří řešit
původní, poměrně obtížné úlohy z různých oblastí teoretické matematiky,
která se zabývá otázkami, jimž nějaké bezprostřední praktické uplatnění
5
často zjevně chybí. Kupříkladu v souvislosti s hrou sudoku některé matematiky
počátkem 21. století napadla otázka, jakým postupem zjistit počet N
všech správných tabulek sudoku z číslic 1 až 9. Zdůrazňuji, že předmětem
zájmu těchto matematiků nebyla samotná hodnota
N = 6 670 903 752 021 072 936 960
.
= 6,67 · 1021
;
prakticky vzato, je totiž úplně jedno, zda je to číslo řádu 1021
nebo třeba
„jen 1018
. Tyto matematiky více zajímal samotný postup, jak se k hodnotě
N dobrat, když zjevně je zhola nemožné na počítači probrat všechny
tabulky 9 × 9, a to ani při triviálních redukcích, které každého matematika
rychle napadnou.
Historicky první zveřejnění čísla N se datuje do roku 2003, když na
dotyčné internetové stránce neznámý autor pod značkou QSCGZ nepodal
žádné vysvětlení svého výpočtu. Teprve v roce 2006 se na internetu objevil
příspěvek
• Bertram Felgenhauer, Frazer Jaris: Enumerating possible Sudoku grids,
v němž autoři hodnotu N ohlášenou v roce 2003 potvrdili a podložili pěknými
matematickými úvahami, spojenými, nutno přiznat, s rozsáhlými,
avšak v reálném čase zvládnutelnými výpočty na počítači.
Nebojte se, tyto úvahy dnes tady rozvádět nebudu. Poznamenám jen, že
v mnoha pojednáních o tabulkách sudoku se hodnota N zapisuje ve tvaru
součinu
N = 9! · 722
· 27
· 27 704 267 971,
kde poslední činitel je prvočíslo. Věřím, že nejen pro přítomné soutěžící bude
srozumitelné následující vysvětlení, proč je číslo N skutečně násobkem čísla
9! · 722
. K tomu nám stačí ukázat, že všechny tabulky sudoku lze rozdělit
do stejněpočetných skupin po 9! · 722
exemplářích.
Vezměme tedy jednu tabulku sudoku, která má v levém horním rohu
6
číslice od 1 po 9 v pořadí jako na dalším obrázku.
1 2 3 ⋆ ⋆ ⋆ ⋆ ⋆ ⋆
4 5 6 ⋆ ⋆ ⋆ ⋆ ⋆ ⋆
7 8 9 ⋆ ⋆ ⋆ ⋆ ⋆ ⋆
⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆
⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆
⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆
⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆
⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆
⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆
Z této tabulky budeme získávat další tabulky sudoku se stejným levým
horním blokem, jaký má původní tabulka, a to kombinacemi těchto úprav:
permutacemi prostřední trojice řádků, permutacemi dolní trojice řádků, výměnou
prostředního a spodního pruhu trojice řádků, a podobnými permutacemi
prostředních a pravých trojic sloupců a výměnou obou příslušných
pruhů trojic sloupců. Popsaných permutací posledních šesti řádků (včetně
jejich původního pořadí) je 6 · 6 · 2 = 72, právě tolik je i popsaných permutací
posledních šesti sloupců. Úvahou o číslech zapsaných v prvním řádku
a prvním sloupci výsledných tabulek zjistíme, že popsaným způsobem jsme
vnořili jednu výchozí tabulku do skupiny 722
různých tabulek. Každou takovou
skupinu pak početně zvětšíme 9!-krát cestou přeznačení číslic od 1
do 9 jejich libovolnou permutací. Takto zřejmě rozdělíme do oněch skupin
všechny tabulky sudoku. Tím je slíbené vysvětlení u konce. Jen bych chtěl
upozornit, že právě podaná poměrně triviální úvaha o sestavených stejně
početných skupinách tabulek ani zdaleka ještě není dostatečným teoretickým
podkladem pro počítačové určení hledaného čísla N.
Milí přítomní, tabulky sudoku neopustím, ani když teď přejdu k číslu,
které znají všichni školáci z výpočtu obvodu a obsahu kruhu a které hraje
významnou roli i ve vyšší matematice. Má dekadický zápis
3,141592653589793238462643383279502 . . .
Ano, jde o číslo π, v naší části Evropy též zvané Ludolfovo číslo. Jak jsem
se doslechl asi před rokem v Českém rozhlase, podotýkám že to nebylo
7
v magazínu Meteor, nýbrž v pásmu Dobré ráno, Česko!, tak přestože už jsou
známy bilióny číslic čísla π za desetinnou čárkou, nejvýkonnější počítače
současnosti objevují jeho další a další číslice, a proto pořád není jasné,
zdali to číslo π vůbec někde končí (sic!).
Soustřeďme se však pouze na vypsané číslice a povšimněme si, že první
nula čísla π se nachází relativně daleko za desetinnou čárkou. Což takhle
dostat co největší počet předchozích číslic po skupinách do řádků nějaké
kuriózní tabulky sudoku, sestavené jako obvykle z číslic od jedničky po
devítku? Když jsem o tomto svém podivínském nápadu nic na internetu
nenašel, pustil jsem se sám do následujících úvah. Do prvního řádku tabulky
bychom mohli dostat pouze trojčíslí 314,
3,141592653589793238462643383279502 . . . ,
většímu počtu číslic už brání následující jednička. Zato v dalším využitém
řádku tabulky by mohlo být pětičíslí 15926,
3,141592653589793238462643383279502 . . . ,
za kterým ovšem následuje už zastoupená pětka. Podobně v dalším řádku
by mohlo být pouze dvojčíslí 53, v dalším čtyřčíslí 5897, v dalším trojčíslí
932, v dalším pětičíslí 38462:
3,141592653589793238462643383279502 . . .
Pokud to počet řádků a požadovaná sudokost tabulky dovolí, do některých
jejích dalších řádků bychom ještě mohli dostat trojčíslí 643, dvojčíslí 38 a,
v ideálním případě, i pětičíslí 32795, za kterým už následuje osudná nula:
3,141592653589793238462643383279502 . . .
Povšimněte si prosím nečekané náhody: vytvořili jsme celkem devět skupin
číslic, tedy právě tolik, kolik je všech řádků každé tabulky sudoku (sic!). Podobná
souhra okolností zapůsobí na mysl matematika okamžitým účinkem
tak, jako na duši zloděje zvuk krátkého zaklapnutí želízek. Ano, matematik
je vskutku polapen a v následující hodiny, dny a často i delší časové údobí
jen stěží odvrací svou mysl od dotyčného problému, doslova se přemáhá,
aby se zabýval také něčím jiným, co se od něj v práci nebo doma očekává.
8
Věnujme se však věcně, s minimem emocí, nastolené konkrétní otázce:
Je možné v následující tabulce
3 1 4
1 5 9 2 6
5 3
5 8 9 7
9 3 2
3 8 4 6 2
6 4 3
3 8
3 2 7 9 5
posunout předepsané skupiny číslic v jednotlivých řádcích tak, abychom tím
získali správný základ pro sestavení některé tabulky sudoku? Není těžké
se přesvědčit, že existují desítky postavení oněch skupin, které vypadají
nadějně v tom smyslu, že zastoupené číslice v jednotlivých řádcích, sloupcích
i blocích jsou navzájem různé. Ukáži vám kupříkladu jedno (z 13 možných)
nadějných postavení, kdy trojice 314 zůstane v původní poloze:
3 1 4
1 5 9 2 6
5 3
5 8 9 7
9 3 2
3 8 4 6 2
6 4 3
3 8
3 2 7 9 5
9
A k tomu ještě jedno postavení, při kterém je trojice 314 posunuta o 1 pole
doprava:
3 1 4
1 5 9 2 6
5 3
5 8 9 7
9 3 2
3 8 4 6 2
6 4 3
3 8
3 2 7 9 5
Začnete-li třeba namátkou tato postavení testovat, tj. brát je jako zadání
hry sudoku a určovat pak další číslice, které logicky patří do dosud neobsazených
polí, brzy získáte pocit, že byste museli mít štěstí jako v loterii,
abyste celou tabulku správně vyplnili. Zpravidla již po několika krocích
vždy s rozčarováním zjistíte, že dané výchozí postavení je pro hru sudoku
chybné. Co je však ještě více deprimující, nemůžete vyloučit, že některé
postavení je přece jen správné, dokud všechny možnosti systematicky neproberete.
Nesvěříte-li to testování počítači, může být každá vaše chvilková
nepozornost osudná.
Hypotézu o málo pravděpodobné existenci správného postavení devíti
skupin se mi posléze podařilo podpořit způsobem, který lze ověřit bez počítače,
tedy s tužkou a papírem. Při něm se nejprve soustředíme pouze na
skupiny číslic 5897, 932 a 38462 pro prostřední trojici řádků. Poměrně rychle
lze zjistit, že tato trojice má pouze 24 nadějných vzájemných rozestavení a
10
že z těchto 24 zadání hry sudoku pouze jediné není chybné a vypadá takto:
5 8 9 7 1
9 3 2 5
3 8 4 6 2
Ke třem červeně vyznačeným skupinám číslic jsme rovnou ještě připsali
modře zbylé dvě číslice, které pak patří do prostředního bloku: zřejmě pětka
pod jedničku.
Nyní vezmeme do hry pětici číslic 15926 pro druhý řádek a podíváme
se, kam bychom ji mohli nadějně umístit. Snadno zjistíme, že pro ni máme
jedinou možnou pozici:
1 5 9 2 6
5 8 9 7 1
9 3 2 5
3 8 4 6 2
Teď podobně otestujeme pětici 32795 pro poslední řádek. Zjistíme, že žádnou
nadějnou pozici tato pětice už nemá, a tím se náš sen definitivně rozplývá.
Ač neradi, zdůvodnili jsme právě, že kýžené postavení všech devíti
skupin číslic π neexistuje. Zbývá se jen ujistit, zdali člověk něco nepřehlédl,
zejména znovu projít všech 24 postavení pro prostřední trojici řádků. Pak
už se můžeme, podle osobního vkusu, jen oddat nějaké formě truchlení.
11
Novou naději, jak do jedné tabulky sudoku dostat po řádcích všechny číslice
π až po první nulu, mi přinesl nečekaný nápad: K určenému rozestavení
skupin číslic 5897, 932 a 38462 v prostřední trojici řádků nadějně připsat
pětice 15926 a 32795 do patřičných řádků tak, že první pětici „roztrhneme
následujícím způsobem:
5 9 2 6 1
5 8 9 7 1
9 3 2 5
3 8 4 6 2
3 2 7 9 5
Tato „roztržka bude mít zatraceně dobrý smysl, když tabulku svineme a
po obou svislých hranách slepíme do tvaru válce, na jehož plášti pak bude
pětičíslí 15926 souvislé. Ani sudokost takto svinuté tabulky svůj význam
neztratí!
Po této resuscitaci už vše další šlo ráz naráz, ani netušíte jak rychle.
Snadno se našly nadějné pozice pro zbývající skupiny číslic (když i trojice
643 musela být roztržena) a — světe div se — doplnění do tabulky sudoku
bylo poté podobně jednoduchým úkonem, jakým si šťastlivec kupuje v loterii
vítězný los.
12
Číslice π po první nulu
8 3 1 4 5 7 9 2 6
5 9 2 6 8 3 4 7 1
7 4 6 2 1 9 5 3 8
2 5 8 9 7 1 6 4 3
4 6 9 3 2 5 8 1 7
1 7 3 8 4 6 2 5 9
3 2 5 7 9 8 1 6 4
9 1 7 5 6 4 3 8 2
6 8 4 1 3 2 7 9 5
c J. Šimša, 2016
Zhmotněný výsledek mého snažení vám teď předvedu in natura. Je to
onen suvenýr, který jsem před chvílí předal svým přátelům. Exemplář, který
držím v ruce, teď rád věnuji paní Soně Křišťanové, předsedkyni krajské
komise MO Pardubického kraje. ( . . . )
Dámy a pánové, v úplném závěru svého vystoupení chci popřát všem
soutěžícím hodně vytrvalosti a šťastných nápadů při řešení nesnadných matematických
úloh a úspěšná překonávaní dílčích nezdarů, což si ovšem nebudou
moci usnadňovat jako já lepením svých protokolů do ruliček. Svůj
dnešní projev ukončím ještě jednou původní písmenkovou tabulkou sudoku:
H M E T ! C V I A
V A T I H E M ! C
C I ! V M A T H E
! C M A T I E V H
T V I M E H C A !
E H A ! C V I T M
A ! V E I M H C T
M T H C V ! A E I
I E C H A T ! M V
Vivat Mathematica!
13