Univerzita Karlova v Praze Matematicko-fyzikální fakulta. Klasické kombinatorické úlohy. Katedra didaktiky matematiky

Univerzita Karlova v Praze Matematicko-fyzik´aln´ı fakulta

´ PRACE ´ DIPLOMOVA

Krist´yna Stodolov´a Klasick´ e kombinatorick´ eu ´ lohy Katedra didaktiky matematiky

Vedouc´ı diplomov´e pr´ace: RNDr. Anton´ın Slav´ık, Ph.D. Studijn´ı program: Matematika Studijn´ı obor: Uˇcitelstv´ı matematiky-informatiky pro stˇredn´ı ˇskoly

Praha 2012

Ze srdce dˇekuji sv´emu vedouc´ımu pr´ace za jeho ˇcas, spolehlivost, dobr´e rady, nezniˇcitelnou trpˇelivost, vstˇr´ıcn´ y pˇr´ıstup a citelnou podporu.

Zdaˇril´e kous´ıˇcky t´eto pr´ace bych r´ada vˇenovala sv´emu dˇedovi, Janu Tom´aˇsovi.

Prohlaˇsuji, ˇze jsem tuto diplomovou pr´aci vypracovala samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u, literatury a dalˇs´ıch odborn´ ych zdroj˚ u. Beru na vˇedom´ı, ˇze se na moji pr´aci vztahuj´ı pr´ava a povinnosti vypl´ yvaj´ıc´ı ze z´akona ˇc. 121/2000 Sb., autorsk´eho z´akona v platn´em znˇen´ı, zejm´ena skuteˇcnost, ˇze Univerzita Karlova v Praze m´a pr´avo na uzavˇren´ı licenˇcn´ı smlouvy o uˇzit´ı t´eto pr´ace jako ˇskoln´ıho d´ıla podle §60 odst. 1 autorsk´eho z´akona.

V Praze dne 10. 4. 2012

Krist´ yna Stodolov´a

N´azev pr´ace: Klasick´e kombinatorick´e u ´lohy Autor: Krist´ yna Stodolov´a Katedra: Katedra didaktiky matematiky Vedouc´ı diplomov´e pr´ace: RNDr. Anton´ın Slav´ık, Ph.D. Abstrakt: Pr´ace se vˇenuje pˇeti u ´loh´am z kombinatoriky. V u ´loze o zajatc´ıch je ˇreˇseno, kdo ze zajatc˚ u stoj´ıc´ıch v kruhu ˇci ˇradˇe pˇreˇzije, je-li postupnˇe popravov´an kaˇzd´ y q-t´ y. Zahrnuta je i varianta s v´ıce ˇzivoty. V u ´loze o hanojsk´ ych vˇeˇz´ıch jsou zkoum´any poˇcty a vlastnosti tah˚ u kotouˇc˚ u pˇren´aˇsen´ ych mezi tˇremi nebo ˇctyˇrmi kol´ıky vˇcetnˇe omezen´ı pˇr´ıpustn´ ych tah˚ u. V u ´loze o hostech jsou poˇc´ıt´ana rozesazen´ı manˇzelsk´ ych p´ar˚ u kolem stolu stˇr´ıdaj´ıc´ı muˇze a ˇzeny, kde ˇza´dn´ y p´ar nesed´ı vedle sebe. N´asleduj´ı permutace s omezuj´ıc´ımi podm´ınkami a vˇeˇzov´e polynomy. U hlasovac´ıho probl´emu je urˇcov´ana pravdˇepodobnost, ˇze jeden z kandid´at˚ u mˇel po celou dobu voleb v´ıc neˇz k-n´asobek poˇctu hlas˚ u druh´eho. Zm´ınˇena jsou Catalanova ˇc´ısla. V u ´loze o ˇskolaˇck´ach je sestavov´an t´ ydenn´ı rozpis vych´azek patn´acti d´ıvek ve trojic´ıch tak, aby spolu ˇz´adn´e dvˇe neˇsly v´ıcekr´at. N´asleduj´ı u ´loha o golfistech a Schurigovy tabulky. Kl´ıˇcov´a slova: u ´loha o zajatc´ıch, hanojsk´e vˇeˇze, u ´loha o hostech, hlasovac´ı probl´em, u ´loha o ˇskolaˇck´ach

Title: Classic problems in combinatorics Author: Krist´ yna Stodolov´a Department: Department of Mathematics Education Supervisor: RNDr. Anton´ın Slav´ık, Ph.D. Abstract: This work is concerned with five problems in combinatorics. In Josephus problem, people are standing in a circle or in a row and every q-th is executed until only one person remains. We show how to find the survivor, and discuss the generalization when each person has more lives. In Tower of Hanoi, we study the numbers and properties of moves necessary to transport the tower from one rod to another, where the total number of rods is either three or four. We mention related problems with restrictions on the legal moves. In m´enage problem, we calculate the number of seatings of couples around a table such that men and women alternate and nobody sits next to his or her partner. We also discuss permutations with restricted positions and rook polynomials. In ballot problem, we consider two candidates competing against each other and calculate the probability that, throughout the count, the first candidate always had more votes than k times the number of votes of the second one; we also mention the relation to Catalan numbers. In Kirkman’s schoolgirl problem, the task is to find a weekly schedule for fifteen girls walking daily out in triads so that no two go together more than once. We also discuss the social golfer problem and Schurig’s tables. Keywords: Josephus problem, Tower of Hanoi, m´enage problem, ballot problem, Kirkman’s schoolgirl problem

Obsah ´ Uvod

2

´ 1 Uloha o zajatc´ıch 1.1 Z´akladn´ı varianta . . . . . . . . . . . . . 1.2 Z´achrana pˇr´ıtele . . . . . . . . . . . . . . 1.3 Obecnˇejˇs´ı probl´em a moˇznost urˇcit ˇc´ıslo 1.4 V´ıce ˇzivot˚ u . . . . . . . . . . . . . . . . 1.5 V ˇradˇe m´ısto v kruhu . . . . . . . . . . . 2 Hanojsk´ e vˇ eˇ ze 2.1 Z´akladn´ı varianta . . . . ˇ sen´ı trochu jinak . . . 2.2 Reˇ 2.3 Pˇr´ıˇserky a koule . . . . . 2.4 Pozmˇenˇen´a zad´an´ı . . . 2.5 Hanojsk´e vˇeˇze na ˇctyˇrech ´ 3 Uloha o hostech 3.1 Pˇr´ımoˇcar´e ˇreˇsen´ı . 3.2 Vˇeˇzov´e polynomy . 3.3 Kdyˇz uˇz sed´ı ˇreditel 3.4 Nˇekolik pozn´amek .

. . . .

. . . .

. . . .

. . . . . . . . . . . . . . . . . . . . kol´ıc´ıch

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

4 Hlasovac´ı probl´ em ˇ 4.1 Reˇsen´ı pomoc´ı pˇreklopen´ı . . . . . . ˇ sen´ı pomoc´ı otoˇcen´ı . . . . . . . . 4.2 Reˇ ˇ sen´ı pomoc´ı matematick´e indukce . 4.3 Reˇ ˇ sen´ı uspoˇra´d´an´ım do kruhu . . . . 4.4 Reˇ ˇ sen´ı pomoc´ı kl´ıˇcov´ 4.5 Reˇ ych vrchol˚ u. . . 4.6 Souvislost s Catalanov´ ymi ˇc´ısly . . .

. . . . .

. . . .

. . . . . .

´ 5 Uloha oˇ skolaˇ ck´ ach 5.1 Pˇr´ımoˇcar´e ˇreˇsen´ı . . . . . . . . . . . . 5.2 Algebraick´e ˇreˇsen´ı . . . . . . . . . . . . 5.3 Geometrick´a ˇreˇsen´ı – krychle a ˇctyˇrstˇen 5.4 Geometrick´e ˇreˇsen´ı – pyramida . . . . ´ 5.5 Uloha o golfistech a Schurigovy tabulky

. . . . .

. . . .

. . . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . . .

3 3 6 7 9 10

. . . . .

12 12 14 16 18 21

. . . .

25 25 27 32 35

. . . . . .

37 37 39 40 40 42 43

. . . . .

45 45 46 48 52 54

Z´ avˇ er

57

Seznam pouˇ zit´ e literatury

59

1

´ Uvod Dost´av´a se v´am do rukou pr´ace, kter´a si klade za c´ıl shrom´aˇzdit na jednom m´ıstˇe poznatky o nˇekter´ ych kombinatorick´ ych u ´loh´ach, jimiˇz se matematici zaob´ıraj´ı uˇz d´ele neˇz sto let a jeˇz jsou ve svˇetˇe pomˇernˇe zn´amy. Urˇcena je pro vˇsechny z´ajemce o kombinatoriku, kteˇr´ı si chtˇej´ı rozˇs´ıˇrit obzory a poznat, ˇze tento obor nekonˇc´ı u vzorc˚ u pro poˇcty permutac´ı a variac´ı, n´ ybrˇz tyto jsou jen prvn´ım krokem na dlouh´e cestˇe vpˇred. Obsah pr´ace by mˇel b´ yt srozumiteln´ y i matematicky nadanˇejˇs´ım student˚ um stˇredn´ıch ˇskol, pˇredpokl´ad´a ale jistou d´avku samostatnosti pˇri dostudov´an´ı nepˇr´ıliˇs sloˇzit´ ych, avˇsak jim dosud nezn´am´ ych pojm˚ u. Text je ˇclenˇen do pˇeti kapitol, kaˇzd´a z nich se vˇenuje jedn´e konkr´etn´ı u ´loze. V u ´vodu je vˇzdy struˇcnˇe pops´ana jej´ı historie a vysvˇetleno zad´an´ı. Zpravidla n´asleduje nˇekolik zp˚ usob˚ u ˇreˇsen´ı a r˚ uzn´e varianty zad´an´ı. V z´avˇeru se pak objevuje zobecnˇen´ı u ´lohy nebo souvislosti s dalˇs´ımi partiemi kombinatoriky. Prvn´ı kapitola se zab´ yv´a u ´lohou o zajatc´ıch. Ti stoj´ı v kruhu a postupnˇe je kaˇzd´ y druh´ y z nich popravov´an aˇz do chv´ıle, kdy zb´ yv´a posledn´ı, jenˇz dostane milost. Je uk´az´ano, kdo z nich to bude. N´asleduj´ı varianty, kdy je popravov´an kaˇzd´ y q-t´ y a hled´a se takov´e q, aby pˇreˇzili urˇcit´ı zajatci. D´ale jsou pops´any i situace s v´ıce ˇzivoty nebo s uspoˇra´d´an´ım v ˇradˇe m´ısto v kruhu. Druh´a kapitola pojedn´av´a o hanojsk´ ych vˇeˇz´ıch. Kromˇe poˇctu tah˚ u potˇrebn´ ych k pˇrenesen´ı kotouˇc˚ u z jednoho kol´ıku na jin´ y ukazuje, jak´ ym zp˚ usobem se jednotliv´e kotouˇce pohybuj´ı a stˇr´ıdaj´ı v taz´ıch. Pot´e je vˇenov´an prostor variant´am, kde je pˇr´ım´ y pˇrenos kotouˇc˚ u mezi nˇekter´ ymi kol´ıky zak´az´an nebo jsou ˇctyˇri kol´ıky m´ısto tˇr´ı. Pro zpestˇren´ı je uvedena i u ´loha o pˇr´ıˇserk´ach, kter´a se d´a pˇrev´est na probl´em hanojsk´ ych vˇeˇz´ı. T´ematem tˇret´ı kapitoly je u ´loha o hostech. Poˇc´ıt´a se, kolika zp˚ usoby je moˇzn´e rozesadit nˇekolik manˇzelsk´ ych p´ar˚ u okolo stolu tak, aby se muˇzi a ˇzeny stˇr´ıdali a nikdo nesedˇel vedle sv´eho partnera. N´asleduje jej´ı zobecnˇen´ı na permutace s omezuj´ıc´ımi podm´ınkami. Zde je zm´ınˇena i teorie vˇeˇzov´ ych polynom˚ u. ˇ Ctvrt´a kapitola je vyhrazena pro hlasovac´ı probl´em. V nˇem se m´a urˇcit pravdˇepodobnost, ˇze prvn´ı kandid´at mˇel po celou dobu sˇc´ıt´an´ı hlasovac´ıch l´ıstk˚ u v´ıc neˇz k-n´asobek poˇctu hlas˚ u druh´eho. Zde je zaj´ımav´e, ˇze existuje velk´ y poˇcet r˚ uzn´ ych zp˚ usob˚ u, jak dospˇet k v´ ysledku. V z´avˇeru je uvedena varianta t´eto u ´lohy, kdy je poˇzadov´ano, aby prvn´ı kandid´at mˇel alespoˇ n tolik hlas˚ u jako druh´ y, a je uk´az´ano, ˇze vede na Catalanova ˇc´ısla. ´ P´at´a kapitola patˇr´ı u ´loze o ˇskolaˇck´ach. Ukolem je sestavit t´ ydenn´ı rozpis vych´azek pro patn´act d´ıvek chod´ıc´ıch ve trojic´ıch tak, aby kaˇzd´a s kaˇzdou ˇsla pr´avˇe jednou. Uk´az´ano je nˇekolik ˇreˇsen´ı, algebraick´ ych a hlavnˇe geometrick´ ych. Z´avˇer je vˇenov´an zobecnˇen´emu probl´emu, u ´loze o golfistech. Uk´az´any jsou i s t´ımto souvisej´ıc´ı Schurigovy tabulky, kter´e slouˇz´ı jako rozpis jednotliv´ ych kol napˇr´ıklad ˇsachov´ ych turnaj˚ u, v nichˇz se m´a utkat kaˇzd´ y hr´aˇc s kaˇzd´ ym.

2

´ 1. Uloha o zajatc´ıch N´asleduj´ıc´ı u ´loha, ve svˇetˇe zn´am´a jakoˇzto Josephus Problem, n´as sv´ ym ponˇekud morbidn´ım znˇen´ım odkazuje do dob prvn´ıho stolet´ı naˇseho letopoˇctu, kdy zuˇrila ˇ ˇ ımany. Vypr´av´ı se, ˇze ˇzidovsk´ v´alka mezi Zidy a R´ y knˇez a uˇcenec Josephus se se skupinou dalˇs´ıch muˇz˚ u dostal do obkl´ıˇcen´ı ˇr´ımsk´ ym vojskem. V beznadˇejn´e situaci jeho spoleˇcn´ıci zvolili radˇeji smrt rukou sv´ ych pˇr´atel, neˇz aby upadli v potupn´e zajet´ı. Shrom´aˇzdili se proto do kruhu a postupnˇe byl zab´ıjen kaˇzd´ y druh´ y muˇz. Josephus, kter´ y tento pˇr´ıstup neschvaloval, rychle vypoˇcetl kam se postavit, aby z˚ ustal posledn´ım pˇreˇzivˇs´ım. Pozdˇeji byl osvobozen, pˇrijal jm´eno Flavius a vstoupil ˇ ıma. Z˚ do sluˇzeb R´ ustal vˇsak vˇern´ y ˇzidovsk´e v´ıˇre a tradici. Sepsal historicky cenn´a d´ıla o sv´e dobˇe. Pˇresnˇejˇs´ı a podrobnˇejˇs´ı informace jsou v [12].

1.1

Z´ akladn´ı varianta

´ Uloha 1. V kruhu stoj´ı n zajatc˚ u. Postupnˇe je kaˇzd´y druh´y popraven, jen posledn´ı dostane milost. Kter´y z nich to bude? Zajatce oznaˇc´ıme ˇc´ısly 1, . . . , n ve smˇeru hodinov´ ych ruˇciˇcek. V tomto smˇeru budeme t´eˇz poˇc´ıtat. Necht’ J(n) je ˇc´ıslo omilostnˇen´eho zajatce. Napˇr. pro n = 11 jsou zajatci popravov´ani v poˇrad´ı 2, 4, 6, 8, 10, 1, 5, 9, 3, 11 a J(n) = 7 (viz obr. 1.1). 6 10

11 5

8

1

1

2

10

3

9

4 8

4

9

2

5 7

6

7

3

Obr´azek 1.1: V z´akladn´ı variantˇe u ´lohy o zajatc´ıch pˇreˇzije z jeden´acti ten sedm´ y. ˇ sen´ı u Reˇ ´lohy najdeme napˇr. v [11] a [15]. Neprozrad´ıme si ho hned na u ´vod, ale postupnˇe k nˇemu dojdeme. Zˇrejmˇe J(1) = 1, tj. je-li jedin´ y zajatec, dostane milost. Pro vˇetˇs´ı n se zamysleme nad t´ım, kolik zajatc˚ u zbyde po prvn´ım koleˇcku a kteˇr´ı to budou. Je-li n sud´e, ˇcili n = 2k, zbyde pˇresnˇe k zajatc˚ u s ˇc´ısly 1, 3, 5, . . . , 2k − 1. Je-li n lich´e, n = 2k + 1, pak bˇehem prvn´ıho koleˇcka odstran´ıme vˇsech k zajatc˚ u se sud´ ymi ˇc´ısly a hned po nich bude urˇcitˇe n´asledovat zajatec ˇc´ıslo 1. Zbyde n´am tedy opˇet k zajatc˚ u, tentokr´at s ˇc´ısly 3, 5, 7, . . . , 2k + 1. Tak ˇci tak se n´aˇs probl´em zredukuje na hled´an´ı J(k), jenom na r-t´e pozici ted’ stoj´ı zajatec s ˇc´ıslem 2r − 1, 3

resp. 2r + 1, r = 1, 2, . . . , k. Pokud J(k) zn´ame, snadno uˇz dopoˇc´ıt´ame J(n). Odtud dost´av´ame rekurentn´ı vztahy: J(1) = 1 J(2k) = 2J(k) − 1 pro k ≥ 1 J(2k + 1) = 2J(k) + 1 pro k ≥ 1. Nyn´ı bychom se r´adi dopracovali k explicitn´ımu vyj´adˇren´ı J(n). Sestavme si tabulku pro nˇekolik prvn´ıch hodnot n. n J(n)

1 2 1 1

3 3

4 1

5 3

6 5

7 8 7 1

9 3

10 11 5 7

12 13 14 15 16 9 11 13 15 1

17 3

M˚ uˇzeme si vˇsimnout, ˇze J(n) = 1 pro n = 1, 2, 4, 8, 16, ˇcili pro mocniny dvojky. Jedniˇckou poˇc´ınaje se hodnota J(n) postupnˇe zvyˇsuje o 2. Snadno tak dospˇejeme k hypot´eze, ˇze pro n = 2m + l, kde 0 ≤ l < 2m , plat´ı J(n) = 2l + 1.

(1.1)

Tuto hypot´ezu dok´aˇzeme indukc´ı podle m. V prvn´ım kroku m´ame m = 0, l m˚ uˇze nab´ yvat pouze hodnoty 0. Dost´av´ame J(1) = 1, coˇz plat´ı. V dalˇs´ım kroku pˇredpokl´ad´ame, ˇze vztah plat´ı pro 1, . . . , m − 1. Uk´aˇzeme, ˇze pak plat´ı i pro m. Zamˇeˇr´ıme se zvl´aˇst’ na situace, kdy je l sud´e a kdy je lich´e. Pro sud´e l dost´av´ame     l l m m−1 − 1 = 2 2 · + 1 − 1 = 2l + 1. J(2 + l) = 2J 2 + 2 2 Podobnˇe pro lich´e l m



m−1

J(2 + l) = 2J 2

l−1 + 2



  l−1 + 1 + 1 = 2l + 1. +1=2 2· 2

T´ımto je naˇse hypot´eza potvrzena. D´ale si uvˇedom´ıme, ˇze m = blog2 nc. ∗ Dospˇeli jsme tedy k v´ ysledku
J(n) = 2 n − 2blog2 nc + 1 = 2n + 1 − 2blog2 nc+1 . (1.2) Pro zaj´ımavost zmiˇ nme, ˇze tento v´ ysledek m´a pˇeknou a jednoduchou interpretaci ˇskrtni prvn´ı jedniˇcku a napiˇs ji na konec“, pracujeme-li s ˇc´ısly n a J(n) Pm ” j ˇ ve dvojkov´e soustavˇe. C´ıslo n m˚ uˇzeme ps´at jako n = j=0 bj 2 , kde bj = 1 nebo 0 P j pro j = 1, . . . , m−1 a bm = 1. Potom l = n−2m = m−1 ze l dostaneme j=0 bj 2 . Takˇ z n t´ım, ˇze smaˇzeme prvn´ı jedniˇcku z bin´arn´ıho z´apisu ˇc´ısla n. (M˚ uP ˇzeme smazat j+1 i vˇsechny nuly pˇredch´azej´ıc´ı dalˇs´ı jedniˇcce). D´ale dost´av´ame 2l = m−1 . j=0 bj 2 Dvˇema vlastnˇe n´asob´ıme tak, ˇze na konec ˇc´ısla pˇrip´ıˇseme nulu. Nyn´ı zb´ yv´a pˇriˇc´ıst jedniˇcku, to udˇel´ame tak, ˇze nulu, kterou jsme pˇripsali na konec, zmˇen´ıme na jedniˇcku. ∗

bxc znaˇc´ı doln´ı celou ˇc´ ast x

4

Napˇr. pro n = 22 dost´av´ame l = 6 a J(n) = 2 · 6 + 1 = 13. Ve dvojkov´e soustavˇe: n = 10110 l = 110 2l = 1100 J(n) = 1101 V´ıce podrobnost´ı je moˇzno naj´ıt v [11] nebo ˇcesky psan´em ˇcl´anku [15]. Nyn´ı se uˇz ale pod´ıv´ame, jak´ ym jin´ ym zp˚ usobem by se dalo ke vzorci (1.2) dospˇet. Nejdˇr´ıv si uvˇedom´ıme, ˇze je-li poˇcet zajatc˚ u mocninou dvojky, bude pˇreˇzivˇs´ım vˇzdy zajatec ˇc´ıslo 1, ˇcili J(2m ) = 1. Myˇslenka je takov´a, ˇze pˇri kaˇzd´em koleˇcku m´ame sud´ y poˇcet zajatc˚ u, vˇzdy je tedy popraven posledn´ı zajatec a na poˇca´tku dalˇs´ıho koleˇcka se zaˇc´ın´a poˇc´ıtat od zajatce ˇc´ıslo 1, ten tak nikdy nen´ı druh´ y“ ” a zbyde aˇz do sam´eho konce. Dalˇs´ım uˇziteˇcn´ ym vztahem (pro obecnˇejˇs´ı znˇen´ı viz [24]) je J(n) ≡ J(n − 1) + 2 (mod n) pro n ≥ 2. (1.3) Ten vypl´ yv´a ze skuteˇcnosti, ˇze m´ame-li n zajatc˚ u a na poˇc´atku je popraven zajatec ˇc´ıslo 2, probl´em se pˇrevede na hled´an´ı J(n − 1). Zaˇc´ın´ame vˇsak poˇc´ıtat od zajatce ˇc´ıslo 3, ˇc´ısla zajatc˚ u jsou tedy o 2 posunuta, proto +2“. Ve vzorci je ” modn“, protoˇze ˇc´ıslo n − 1 se neposunuje na n + 1, n´ ybrˇz na 1. ” Pˇri hled´an´ı vzorce pro J(n) tedy vych´az´ıme ze vztah˚ u: J(2m ) = 1 pro m = 0, 1, 2, . . . ( J(n − 1) + 2 pro J(n − 1) < n − 1 J(n) = 1 pro J(n − 1) = n − 1

(1.4)

Jeˇstˇe si poloˇzme ot´azku, zda existuje k r˚ uzn´e od mocniny dvojky, pro kter´e ’ J(k) = 1. Odpovˇed zn´ı ne. D˚ ukaz provedeme sporem. Mˇejme nejmenˇs´ı k, pro kter´e to plat´ı. Nejbliˇzˇs´ı niˇzˇs´ı mocnina dvojky k tomuto k je 2blog2 kc . Z (1.4) plyne J(k − 1) = k − 1 a tak´e J(k − 1) = 1 + 2 · (k − 1 − 2blog2 kc ), to vzhledem k naˇc´ıt´an´ı ” dvojek“, ˇcili 1 + 2 · (k − 1 − 2blog2 kc ) = k − 1. Odtud po u ´prav´ach k = 2blog2 kc , coˇz je ve sporu s t´ım, ˇze k nen´ı mocninou dvojky. Plat´ı tedy ( 1 n mocnina dvojky J(n) = J(n − 1) + 2 jinak, odkud uˇz pˇr´ımo plyne (1.2), dˇr´ıve odvozen´ y vzorec pro J(n).

5

1.2

Z´ achrana pˇ r´ıtele

V [11] m˚ uˇzeme naj´ıt v souvislosti s u ´lohou o zajatc´ıch n´asleduj´ıc´ı probl´em. ´ Uloha 2. Joseph˚ uv pˇr´ıtel by se mohl zachr´anit t´ım, ˇze se postav´ı na takovou pozici, aby na konci zbyli pouze on a Josephus. Kter´a to je? Neboli pro n ≥ 2 hled´ame I(n), ˇc´ıslo zajatce, kter´ y bude jako posledn´ı popraven, pokud pˇredpokl´ad´ame, ˇze zajatec s ˇc´ıslem J(n) je jedin´ y, kter´ y dostane milost. Pˇri ˇreˇsen´ı m˚ uˇzeme postupovat stejn´ ym zp˚ usobem jako pˇri hled´an´ı J(n). Zcela analogickou u ´vahou dojdeme ke vztah˚ um I(2n) = 2I(n) − 1 pro n ≥ 2 I(2n + 1) = 2I(n) + 1 pro n ≥ 2. Odliˇsn´e vˇsak budou poˇc´ateˇcn´ı podm´ınky. Nam´ısto J(1) = 1 dost´av´ame I(2) = 2 a I(3) = 1. Podobnˇe jako pˇri hled´an´ı J(n) sestav´ıme tabulku nˇekolika prvn´ıch hodnot I(n). n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 I(n) – 2 1 3 5 1 3 5 7 9 11 1 3 5 7 9 11 13 15 17 19 21 23 1 Snadno pak dojdeme k hypot´eze, ˇze pro n = 3 · 2m + l, kde l < 3 · 2m , plat´ı I(n) = 2l + 1. Tu lze dok´azat pomoc´ı indukce, analogicky jako pˇri d˚ ukazu m m+1 m vztahu (1.1). Podotknˇeme jeˇstˇe, ˇze 3 · 2 = 2 + 2 . M˚ uˇzeme proto ps´at I(2m + 2m−1 + l) = 2l + 1 pro l < 2m + 2m−1 . Kdyˇz uˇz um´ıme zjistit, kter´ y zajatec pˇreˇzije a kter´ y bude popraven jako posledn´ı, dozajista leckoho napadne n´asleduj´ıc´ı ot´azka. ´ Uloha 3. V kruhu stoj´ı n zajatc˚ u a postupnˇe je kaˇzd´y druh´y popravov´an. Kdo z nich bude popraven jako a-t´y? T´ımto se podrobnˇe zab´ yv´a [25]. My si uk´aˇzeme, jak dospˇet k rekurentn´ım ˇ ıslo a-t´eho popraven´eho zajatce rovnic´ım a bez d˚ ukazu pak uvedeme v´ ysledek. C´ oznaˇc´ıme Ja (n). Nejdˇr´ıv najdeme pˇr´ısluˇsn´e rekurentn´ı vztahy. Pro n > 1 je jako prvn´ı popraven zajatec 2. Probl´em se n´am tak zredukuje na hled´an´ı (a − 1)-n´ıho popraven´eho z n − 1 zajatc˚ u s t´ım, ˇze ˇc´ısla zajatc˚ u jsou o dvojku posunuta. Toto n´am staˇc´ı k sestaven´ı rovnic  1 pro n = a = 1    2 pro n > 1, a = 1 Ja (n) =  1 pro n, a > 1, Ja−1 (n − 1) = n − 1    Ja−1 (n − 1) + 2 pro n, a > 1, Ja−1 (n − 1) ≤ n − 2. Odsud je moˇzn´e odvodit explicitn´ı vyj´adˇren´ı ( 2a Ja (n) = 2n + 1 − (2n − 2a + 1) · 2blog2 n/(2n−2a+1)c+1 6

pro a ≤ n2 pro a > n2 .

1.3

Obecnˇ ejˇ s´ı probl´ em a moˇ znost urˇ cit ˇ c´ıslo

Nyn´ı budeme uvaˇzovat situaci, kdy je popravov´an ne nutnˇe kaˇzd´ y druh´ y zajatec, n´ ybrˇz kaˇzd´ y q-t´ y. Zajatce, kter´ y za tˇechto okolnost´ı pˇreˇzije, budeme oznaˇcovat ˇc´ıslem J(n, q). Aˇckoliv nen´ı zn´am explicitn´ı vzorec pro v´ ypoˇcet J(n, q), je zde nˇekolik zaj´ımav´ ych ot´azek, kter´e dok´aˇzeme zodpovˇedˇet. Nejprve sestavme rekurentn´ı rovnice pro v´ ypoˇcet J(n, q). Ty vypadaj´ı n´asledovnˇe (pro podrobnosti viz [24]): J(1, q) = 1 J(n, q) ≡ J(n − 1, q) + q

(mod n) pro n > 1

Jedn´a se vlastnˇe o zobecnˇen´ı (1.3). T´ım, ˇze je jako prvn´ı popraven q-t´ y zajatec, se n´aˇs probl´em zredukuje na hled´an´ı J(n − 1, q) s t´ım, ˇze ˇc´ısla jsou o q posunuta. A ted’ uˇz se pod´ıvejme na dalˇs´ı u ´lohu z [11]. ´ Uloha 4. V kruhu stoj´ı 2n zajatc˚ u, prvn´ıch n dobr´ych a dalˇs´ıch n zl´ych. Ukaˇzte, ˇze vˇzdy existuje q (v z´avislosti na n) takov´e, ˇze vˇsichni zl´ı budou popraveni dˇr´ıve neˇz kdokoliv z dobr´ych. Napˇr. pro n = 3, m˚ uˇzeme vz´ıt q = 5. Jako prvn´ı tˇri jsou pak popraveni zajatci s ˇc´ısly 5, 4 a 6. Toto q vˇsak nen´ı jedin´ ym ˇreˇsen´ım. Tˇreba pro q = 52 budou jako prvn´ı popraveni zajatci 4, 6 a 5. Kdyby b´ yvali vˇsichni zl´ı st´ali na prvn´ıch n pozic´ıch, situace by se znaˇcnˇe zjednoduˇsila, staˇcilo by zvolit q = 1. Avˇsak i pro n´aˇs obt´ıˇznˇejˇs´ı pˇr´ıpad dok´aˇzeme existenci q, nebudeme se snaˇzit naj´ıt nejmenˇs´ı vhodn´e, ale prostˇe nˇejak´e. Zat´ımco pro q = 1 by byl v kaˇzd´em kroku popraven zajatec s aktu´alnˇe nejmenˇs´ım ˇc´ıslem, my si d´ame za c´ıl urˇcit takov´e q, aby zajatci byli popravov´ani od konce, ˇcili v kaˇzd´em kroku zajatec s aktu´alnˇe nejvyˇsˇs´ım ˇc´ıslem. Kdyˇz se n´am to podaˇr´ı, budou zˇrejmˇe po n kroc´ıch zb´ yvat jenom ti dobˇr´ı. Je-li popraven posledn´ı zajatec, zaˇc´ın´a se v dalˇs´ım kroku poˇc´ıtat od prvn´ıho. Zb´ yv´a-li pr´avˇe k zajatc˚ u, co mus´ı platit pro q, aby rozpoˇc´ıt´av´an´ı padlo na posledn´ıho z nich? Odpovˇed’ je nasnadˇe. Mus´ı platit, ˇze ˇc´ıslo q je dˇeliteln´e ˇc´ıslem k. Pak po q/k koleˇck´ach poˇc´ıt´an´ı skonˇc´ıme u posledn´ıho zajatce. Poˇzadujeme tedy, aby k dˇelilo q pro k = 2n, 2n−1, . . . , n+1. Abychom tomuto vyhovˇeli, staˇc´ı zvolit q = nsn(n + 1, n + 2, . . . , 2n).∗ Zjistili jsme tedy, ˇze q vˇzdy existuje. Pro pˇr´ıpad se ˇsesti zajatci dost´av´ame q = nsn(4, 5, 6) = 60. Pro toto q budou jako prvn´ı popraveni zajatci 6, 5 a 4. Na tuto u ´lohu m˚ uˇzeme narazit i v [24]. Autor se zde zab´ yv´a i n´asleduj´ıc´ı, podobnou u ´lohou. ´ Uloha 5. V kruhu stoj´ı 2n zajatc˚ u. Ukaˇzte, ˇze vˇzdy existuje q (v z´avislosti na n) takov´e, ˇze jsou jako prvn´ı popraveni vˇsichni zajatci na lich´ych pozic´ıch. Napˇr. zvol´ıme-li pˇri ˇctyˇrech zajatc´ıch q = 5, pak jsou jako prvn´ı popraveni zajatci 1 a 3. ∗

nsn znaˇc´ı nejmenˇs´ı spoleˇcn´ y n´asobek

7

Pouˇzijeme podobn´ y trik jako v´ yˇse. Budeme hledat takov´e q, aby zajatci na lich´ ych pozic´ıch byli popravov´ani od konce, ˇcili v poˇrad´ı 2n − 1, 2n − 3, . . . , 1. Uvˇedom´ıme si, ˇze v tomto pˇr´ıpadˇe hled´ame q takov´e, aby rozpoˇc´ıt´av´an´ı skonˇcilo vˇzdy jedno m´ısto pˇred koncem koleˇcka, tj. v prvn´ım kroku na 2n − 1 a v dalˇs´ıch kroc´ıch vˇzdy dvˇe m´ısta pˇred naposledy vyˇrazen´ ym, coˇz je zajatec s aktu´alnˇe nejvyˇsˇs´ım lich´ ym ˇc´ıslem. Chceme tedy q ≡ −1 (mod k) pro k = 2n, 2n−1, · · · , n+1. Staˇc´ı proto zvolit q = nsn(n + 1, n + 2, . . . , 2n) − 1. Kdyˇz jsme jiˇz z´ıskali zkuˇsenost s ˇreˇsen´ım jednoduˇsˇs´ıch u ´loh, m˚ uˇzeme se odv´aˇznˇe pustit do n´asleduj´ıc´ıho probl´emu, kter´ ym se opˇet zaob´ıraj´ı [11] i [24]. ´ Uloha 6. Josephus zn´a poˇcet lid´ı v kruhu n i pozici j, na kter´e se nach´az´ı. Jeho jedinou nadˇej´ı je zvolit takov´e ˇc´ıslo q, aby zbyl jako posledn´ı. M˚ uˇze si b´yt jist, ˇze patˇriˇcn´e ˇc´ıslo existuje? Pˇri hled´an´ı odpovˇedi n´am pˇrijde vhod Bertrand˚ uv postul´at (viz napˇr. [13]), podle nˇehoˇz pro vˇsechna n > 2 existuje alespoˇ n jedno prvoˇc´ıslo p, kter´e splˇ nuje n/2 < p < n. Vyuˇzijeme i slabˇs´ı podobu ˇc´ınsk´e vˇety o zbytc´ıch (viz napˇr. [28]), kter´a ˇr´ık´a, ˇze jsou-li q a r nesoudˇeln´a ˇc´ısla, potom m´a n´asleduj´ıc´ı soustava rovnic ˇreˇsen´ı: x ≡ a (mod q) x ≡ b (mod r) Oznaˇcme N = nsn(1, 2, . . . , n). D´ale pak zvolme prvoˇc´ıslo p, pro kter´e plat´ı n/2 < p < n. Nejdˇr´ıv budeme pˇredpokl´adat, ˇze Josephus stoj´ı v prvn´ı polovinˇe ˇ ıslo q pak dostaneme jako ˇreˇsen´ı soustavy rovnic kruhu, ˇcili j ≤ n/2. C´ q ≡ 0 (mod N/p) q ≡ j − 1 (mod p). Je tˇreba si uvˇedomit, ˇze p a N/p jsou ˇc´ısla nesoudˇeln´a a ˇze N/p je nejmenˇs´ım spoleˇcn´ ym n´asobkem ˇc´ısel 1 aˇz n vyjma p. Splnˇen´ı prvn´ı rovnice zp˚ usob´ı, ˇze kromˇe kroku, kdy zb´ yv´a pr´avˇe p zajatc˚ u, je vˇzdy popraven zajatec na posledn´ı pozici aktu´aln´ıho koleˇcka, ˇcili pˇredch˚ udce naposledy popraven´eho. Druh´a rovnice pak odpov´ıd´a situac´ı, kdy zajatc˚ u zb´ yv´a pr´avˇe p. V tomto kroku bude popraven (j − 1)-n´ı zajatec od m´ısta, kde zaˇcneme poˇc´ıtat. Protoˇze aˇz do t´e doby budou popravov´ani zajatci z konce kruhu, zaˇcne se poˇc´ıt´an´ı od zajatce ˇc´ıslo 1 a bude tedy popraven zajatec j − 1. Pro q, jehoˇz existence je zaruˇcena d´ıky ˇc´ınsk´e vˇetˇe o zbytc´ıch, budou zajatci popraveni v poˇrad´ı n, n−1, . . . , p+1, j −1, j −2, . . . , 1, p, p−1, . . . , j +1 a Josephus na j-t´em m´ıstˇe pˇreˇzije. (Vyuˇz´ıv´ame zde i skuteˇcnosti, ˇze p > n/2 ≥ j, takˇze se nestane, ˇze by byl Josephus popraven dˇr´ıv, neˇz nastane chv´ıle, kdy zb´ yv´a pr´avˇe p zajatc˚ u.) Podobn´ ym zp˚ usobem m˚ uˇzeme vyˇreˇsit situaci, kdy j > n/2. Tentokr´at dostaneme q z rovnic q ≡ 1 (mod N/p) q ≡ j + 1 − n (mod p). Tady uˇz snadno domysl´ıme, ˇze tentokr´at budou zajatci popravov´ani v poˇrad´ı 1, 2, . . . , n − p, j + 1, j + 2, . . . , n, n − p + 1, n − p + 2, . . . , j − 1. Takˇze v obou pˇr´ıpadech m´a Josephus moˇznost z´achrany. 8

1.4

V´ıce ˇ zivot˚ u

Nyn´ı dejme kaˇzd´emu ze zajatc˚ u do zaˇca´tku z ˇzivot˚ u (tj. vˇsem stejnˇe), kter´e funguj´ı tak, ˇze zajatec je popraven aˇz ve chv´ıli, kdy je na nˇeho uk´az´ano celkem z-kr´at. Do t´e doby z˚ ust´av´a st´at v kruhu, pˇriˇcemˇz aktu´aln´ı poˇcet jeho ˇzivot˚ u rozpoˇc´ıt´av´an´ı nijak neovlivˇ nuje. O t´eto problematice pojedn´av´a [23] a d´av´a odpovˇed’ na dvˇe n´ıˇze zadan´e u ´lohy. Nejdˇr´ıve si jeˇstˇe poloˇzme ot´azku, jestli poˇcet ˇzivot˚ u m˚ uˇze ovlivnit koneˇcn´ y ’ v´ ysledek, tedy to, kdo pˇreˇzije. Odpovˇed zn´ı ano. Napˇr´ıklad pro n = 6 a q = 4, pˇreˇzije pro z = 1 zajatec ˇc´ıslo 5 a pro z = 2 zajatec ˇc´ıslo 3. Na druhou stranu ale uvaˇzme situaci, kdy n a q jsou nesoudˇeln´a. V tomto pˇr´ıpadˇe budou pro libovoln´e z zajatci popravov´ani ve stejn´em poˇrad´ı jako pro z = 1. Proˇc? Protoˇze mezit´ım, kdy je na nˇekoho uk´az´ano poprv´e a podruh´e, je uk´az´ano i na vˇsechny ostatn´ı zajatce. To vede aˇz k tomu, ˇze dˇr´ıv, neˇz je kdokoliv popraven, spotˇrebuje kaˇzd´ y z−1 ˇzivot˚ u a zbyde mu posledn´ı, takˇze vˇsichni vlastnˇe ˇcel´ı t´emuˇz jako pˇri z = 1. Uk´aˇzeme si, jak se Josephus m˚ uˇze zachr´anit i v pˇr´ıpadˇe, ˇze nezn´a pˇresn´ y poˇcet ˇzivot˚ u, kter´ y jim bude pˇridˇelen. N´asleduj´ıc´ı u ´loha je vlastnˇe zobecnˇen´ım u ´lohy 6. ´ Uloha 7. Josephus zn´a poˇcet zajatc˚ u v kruhu n a svoji pozici j. Ukaˇzte, ˇze existuje q, jehoˇz volbou se urˇcitˇe zachr´an´ı pˇri libovoln´em poˇctu ˇzivot˚ u. Moˇzn´a bude trochu pˇrekvapen´ım, ˇze ˇreˇsen´ı je shodn´e s ˇreˇsen´ım u ´lohy 6, ˇcili q splˇ nuj´ıc´ı: Pro j ≤ n/2 q q Pro j > n/2 q q

≡ 0 (mod N/p) ≡ j − 1 (mod p). ≡ 1 (mod N/p) ≡ j + 1 − n (mod p).

(1.5) (1.6) (1.7) (1.8)

Pˇripomeˇ nme, ˇze N je nejmenˇs´ı spoleˇcn´ y n´asobek ˇc´ısel 1, . . . , n a p prvoˇc´ıslo takov´e, ˇze n/2 < p < n. Pro oba pˇr´ıpady se pod´ıv´ame, v jak´em poˇrad´ı bude ukazov´ano na zajatce. Pro 1 < j ≤ n/2 to je nz , (n − 1)z , . . . , (p + 1)z , π z−1 , j − 1, j − 2, . . . , 1, p, p − 1, . . . , j + 1, kde ik znamen´a, ˇze na prvek i (pˇr´ıpadnˇe posloupnost nˇejak´ ych prvk˚ u) bylo uk´az´ano k-kr´at za sebou, a π znaˇc´ı nˇejakou permutaci prvk˚ u 1, . . . , p, kter´a zaˇc´ın´a ´ prvkem j −1. Usek nz , (n−1)z , . . . , (p+1)z je d˚ usledkem vztahu (1.5). D´ıky q ≡ 0 je vˇzdy uk´az´ano na posledn´ıho zajatce. Jestliˇze se tedy zajatec ocitne na posledn´ı pozici, je na nˇeho ukazov´ano tak dlouho, dokud mu nedojdou ˇzivoty. Po popravˇe zajatce (p + 1) zb´ yv´a pr´avˇe p zajatc˚ u. Pro tuto chv´ıli se vˇse ˇr´ıd´ı vztahem (1.6). Protoˇze p je prvoˇc´ıslo a q po dˇelen´ı ˇc´ıslem p ned´av´a zbytek 0, jsou tato ˇc´ısla nesoudˇeln´a. Vˇsem ˇzij´ıc´ım zajatc˚ um nav´ıc zb´ yv´a vˇsech z ˇzivot˚ u, nast´av´a tedy dˇr´ıve popsan´a situace, kdy ˇzivoty vˇsech postupnˇe klesnou na jedin´ y (π z−1 ). Pokraˇcov´an´ı je pak stejn´e jako v u ´loze 6. Pro j = 1 uˇz snadno domysl´ıme, ˇze vˇzdy bude uk´az´ano na aktu´alnˇe posledn´ıho zajatce a Josephus pˇreˇzije bez ztr´aty jedin´eho ˇzivota. 9

Pro j > n/2 bude na zajatce ukazov´ano v poˇrad´ı (1, 2, . . . , n)z−1 , 1, 2, . . . , n − p, j + 1, j + 2, . . . , n, n − p + 1, n − p + 2, . . . , j − 1. Ani zde nen´ı zd˚ uvodnˇen´ı obt´ıˇzn´e, nebot’ (1.7) mj. zaruˇcuje, ˇze pˇri n zajatc´ıch bude popoˇradˇe ukazov´ano na kaˇzd´eho z nich. Kaˇzd´ y tak hned v u ´vodu spotˇrebuje z − 1 ˇzivot˚ u a vˇse n´asleduj´ıc´ı je pak shodn´e jako v u ´loze 6, pˇriˇcemˇz (1.8) zp˚ usob´ı, ˇze po popravˇe prvn´ıch n − p zajatc˚ u, bude n´asledovat zajatec j + 1, ˇc´ımˇz se zajatec j jaksi pˇreskoˇc´ı“ a pˇreˇzije tak aˇz do konce. ” Vid´ıme, ˇze poˇrad´ı popravov´an´ı zajtc˚ u ani v jednom z pˇr´ıpad˚ u nez´avis´ı na poˇctu jejich ˇzivot˚ u. Zjistili jsme tedy, ˇze Josephus se urˇcitˇe m˚ uˇze zachr´anit. Ani v n´asleduj´ıc´ı u ´loze nezn´a Josephus pˇresn´ y poˇcet ˇzivot˚ u. Naˇstˇest´ı v´ı, ˇze od urˇcit´e hodnoty uˇz jejich mnoˇzstv´ı nehraje roli. . . ´ Uloha 8. Josephovi je zn´amo n i q. M´a moˇznost stoupnout si na libovolnou pozici a nav´ıc urˇcit doln´ı hranici poˇctu ˇzivot˚ u, kter´e dostanou. Ukaˇzte, ˇze pro nˇej existuje zp˚ usob, jak se zachr´anit. Z´ajemce nalezne ˇreˇsen´ı ve [23]. Zde je uk´az´ano, ˇze Josephovi staˇc´ı zvolit z = Fn+2 .∗ Pro toto a vˇsechna vˇetˇs´ı z pˇreˇzije vˇzdy tent´ yˇz zajatec.

1.5

Vˇ radˇ e m´ısto v kruhu

Nyn´ı bude m´ıt kaˇzd´ y zajatec zase pouze jedin´ y ˇzivot a u ´loha se pozmˇen´ı jinak. Zajatci nebudou st´at v kruhu, n´ ybrˇz v ˇradˇe. Bude popravov´an kaˇzd´ y druh´ y a v momentˇe, kdy se dojde na konec ˇrady, smˇer se obr´at´ı a bude se postupovat k jej´ımu poˇca´tku. A pozor – zajatci na konc´ıch ˇrady se nepoˇc´ıtaj´ı dvakr´at po sobˇe (t´ım by byl jejich osud ihned zpeˇcetˇen), n´ ybrˇz pouze jednou. Posledn´ı pˇreˇzivˇs´ı dostane milost. Kdo to bude? T´ımto se podrobnˇeji zab´ yv´a [12], a to i pˇr´ıpady, kdy je popravov´an kaˇzd´ y tˇret´ı. My si zde uk´aˇzeme nˇekter´e z´akladn´ı v´ ysledky. ´ Uloha 9. Urˇcete W (n), omilostnˇen´eho z n zajatc˚ u za v´yˇse popsan´ych podm´ınek. Zˇrejmˇe W (1) = 1. D´ale zodpovˇezme, co maj´ı spoleˇcn´eho situace, kdy je n sud´e a kdy lich´e. Zamysleme se, co se stane po prvn´ım pr˚ uchodu ˇradou. Zˇrejmˇe padnou vˇsichni se sud´ ymi ˇc´ısly. Je-li n sud´e, n = 2k, je jako posledn´ı v ˇradˇe popraven zajatec 2k, naˇceˇz se otoˇc´ı smˇer a na 2k − 1 je uk´az´ano jakoˇzto na prv´eho“. Je-li n lich´e, n = 2k − 1, je po popravˇe zajatce 2k − 2 zajatec 2k − 1 ” opˇet oznaˇcen jako prv´ y“, pˇriˇcemˇz se otoˇc´ı smˇer poˇc´ıt´an´ı. V obou pˇr´ıpadech se ” tedy dostaneme do shodn´e situace. Odsud plyne W (2k) = W (2k − 1). Nav´ıc vid´ıme, ˇze zbylo pr´avˇe k zajatc˚ u. Probl´em se tak zredukoval na hled´an´ı W (k) s trochu pozmˇenˇen´ ymi ˇc´ısly, jedniˇcce odpov´ıd´a 2k − 1, dvojce 2k − 3, . . . , ˇc´ıslu k odpov´ıd´a 1, tj. ˇc´ıslu r z nov´e u ´lohy odpov´ıd´a ˇc´ıslo 2k − 2r + 1 z u ´lohy p˚ uvodn´ı. Dost´av´ame tak W (2k) = 2k − 2W (k) + 1. Shrneme-li naˇse zjiˇstˇen´ı, pˇri hled´an´ı W (n) vych´az´ıme ze vztah˚ u W (1) = 1 W (2k) = W (2k − 1) = 2k − 2W (k) + 1 pro k ≥ 1. ∗

(1.9)

Fn znaˇc´ı n-t´e Fibonacciho ˇc´ıslo. Ta definujeme jako F0 = 0, F1 = 1 a Fi = Fi−2 + Fi−1 pro vˇsechna i ≥ 2.

10

Pro zaj´ımavost si sestavme tabulku nˇekolika prvn´ıch hodnot W (n): n W (n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 1 3 3 1 1 3 3 9 9 11 11 9 9 11 11 1 1

Poloˇzme N rovno n nebo n P − 1 tak, aby N bylo lich´e. N m˚ uˇzeme vyj´adˇrit j ve dvojkov´e soustavˇe jako N = m b 2 , kde b = b = 1 a b = 0 nebo 1 pro m 0 j j=0 j j = 1, 2, . . . , m − 1. Uk´aˇzeme, ˇze plat´ı m X bj 2j . (1.10) W (n) = 1 + j=1 j lich´ e

Pouˇzijeme indukci podle n, pˇriˇcemˇz vzhledem k (1.9) staˇc´ı pracovat pouze s lich´ ymi n. V prvn´ım kroku snadno ovˇeˇr´ıme, ˇze vztah (1.10) plat´ı pro vˇsechna n ≤ 10. V druh´em kroku pˇredpokl´ad´ame, ˇze (1.10) plat´ı pro 1, 2, . . . , n − 1 a uk´aˇzeme, ˇze pak plat´ı i pro n, kde n > 10. D˚ ukaz provedeme zvl´aˇst’ pro dva ’ pˇr´ıpady, a to n = 4k − 1 a n = 4k + 1. Necht n = 4k − 1, tj. b0 = b1 = bm = 1 a m X n+1 =1+ bj 2j−2 . (1.11) k= 4 j=2 Pak W (4k − 1) = 4k + 1 − 2W (2k) = 4k + 1 − 2(2k + 1 − 2W (k)) = 4W (k) − 1,   n+1 tj. W (n) = 4W − 1. 4 Pro sud´e k pˇrejdeme ke k − 1 t´ım, ˇze od (1.11) odeˇcteme jedniˇcku a dost´av´ame !   m m X X n+1 j−2 =W bj 2 W =1+ bj 2j−2 . 4 j=2 j=2 j lich´ e

Pro lich´e k je b2 = 0 a dost´av´ame !   m m X X n+1 W = W 20 + bj 2j−2 = 1 + bj 2j−2 . 4 j=3 j=2 j lich´ e

Celkovˇe tedy  W (n) = 4W

n+1 4

 −1=3+

m X j=2 j lich´ e

bj 2j = 1 +

m X

bj 2j .

j=1 j lich´ e

Pˇr´ıpad n = 4k + 1 se uk´aˇze podobnˇe. A co n´am v´ ysledek vlastnˇe ˇr´ık´a? Nap´ıˇseme-li N ∗ ve dvojkov´e soustavˇe, pak z nˇej bin´arn´ı z´apis ˇc´ısla W (n) dostaneme jednoduˇse t´ım, ˇze na posledn´ı pozici ponech´ame jedniˇcku, na pozice pˇr´ısluˇsej´ıc´ı sud´e mocninˇe dvojky nap´ıˇseme nulu a zbyl´e ˇc´ıslice op´ıˇseme. Napˇr. W (45) = 41 vypad´a ve dvojkov´e soustavˇe n´asledovnˇe: n = 101101 W (n) = 101001. ∗

N je rovno n nebo n − 1 tak, aby bylo lich´e.

11

2. Hanojsk´ e vˇ eˇ ze V [19] se doˇcteme: V mˇestˇe Ban´arasu je pr´ y chr´am, v nˇemˇz indick´ y b˚ uh Brah” ma pˇri stvoˇren´ı svˇeta postavil tˇri diamantov´e tyˇcinky a navl´ekl na jednu z nich 64 zlat´ ych krouˇzk˚ u: nejvˇetˇs´ı je vespod a kaˇzd´ y dalˇs´ı je menˇs´ı neˇz pˇredeˇsl´ y. Chr´amov´ı knˇeˇz´ı maj´ı za u ´kol pˇrekl´adat bez ust´an´ı, dnem i noc´ı, tyto krouˇzky z jedn´e tyˇcinky na druhou; pˇritom pouˇz´ıvaj´ı tˇret´ı tyˇcinky jako pomocn´e a dodrˇzuj´ı pravidla – pˇren´aˇset souˇcasnˇe jen jeden krouˇzek a nepokl´adat vˇetˇs´ı na menˇs´ı. Povˇest prav´ı, ˇze aˇz bude pˇreneseno vˇsech 64 krouˇzk˚ u, nastane konec svˇeta. . .“ Pokud t´eto legendˇe uvˇeˇr´ıme, m´ame se ob´avat brzk´eho konce? Nejen na to odpov´ı tato kapitola, jeˇz se zab´ yv´a hanojsk´ ymi vˇeˇzemi, matematick´ ym hlavolamem, kter´ y spatˇril svˇetlo svˇeta roku 1883 v Paˇr´ıˇzi. Jeho autorem byl Edouard Lucas (viz napˇr. [20]).

2.1

Z´ akladn´ı varianta

Nebude-li ˇreˇceno jinak, vych´az´ıme z tˇechto pˇredpoklad˚ u: • Hlavolam sest´av´a ze tˇr´ı kol´ık˚ u (znaˇc´ıme A, B a C) a n kotouˇc˚ u (disk˚ u), kter´e se na tyto kol´ıky daj´ı nasouvat. Pˇritom se kaˇzd´e dva kotouˇce liˇs´ı svoj´ı velikost´ı. • Tahem se rozum´ı sejmut´ı vrchn´ıho kotouˇce z nˇekter´eho kol´ıku a jeho pˇrem´ıstˇen´ı na jin´ y kol´ık, pochopitelnˇe opˇet nahoru. • Plat´ı pravidlo, ˇze vˇetˇs´ı kotouˇc nem˚ uˇze b´ yt um´ıstˇen na menˇs´ım. ´ Uloha 10. Jak´y je minim´aln´ı poˇcet tah˚ u potˇrebn´ych k pˇrem´ıstˇen´ı vˇeˇze o n kotouˇc´ıch z jednoho kol´ıku na jin´y? M˚ uˇzeme pˇredpokl´adat, ˇze vˇsechny kotouˇce jsou na kol´ıku A a naˇs´ım c´ılem je pˇresunout je na C. Minim´aln´ı poˇcet tah˚ u pˇri n kotouˇc´ıch oznaˇc´ıme Hn . Napˇr. pro n = 3 je Hn = 7, viz obr. 2.1.

Obr´azek 2.1: Nejrychlejˇs´ı pˇresun tˇr´ı kotouˇc˚ u z prvn´ıho na posledn´ı kol´ık. Kl´ıˇcovou ot´azkou vedouc´ı k ˇreˇsen´ı je, v jak´e situaci pˇresuneme nejvˇetˇs´ı kotouˇc. Ten mus´ı b´ yt nutnˇe pˇresunut alespoˇ n jednou, z A na C, coˇz je moˇzn´e pouze ve chv´ıli, kdy jsou vˇsechny ostatn´ı kotouˇce na kol´ıku B. Probl´em si tedy m˚ uˇzeme rozdˇelit do tˇr´ı krok˚ u:

12

1. Pˇresuneme n − 1 vrchn´ıch kotouˇc˚ u z A na B. 2. Pˇresuneme nejvˇetˇs´ı kotouˇc z A na C. 3. Pˇresuneme n − 1 kotouˇc˚ u z B na C. Rozmysl´ıme si, ˇze toto ˇreˇsen´ı je optim´aln´ı. Pokud bychom nejvˇetˇs´ı kotouˇc pˇresouvali v´ıc neˇz jednou, nijak t´ım nesn´ıˇz´ıme poˇcet pˇresouv´an´ı ostatn´ıch kotouˇc˚ u. D´ale si uvˇedom´ıme, ˇze nejvˇetˇs´ı kotouˇc nikdy neomezuje pohyby ostatn´ıch a ˇze pˇresouv´an´ı z A na B je stejnˇe n´aroˇcn´e jako pˇresouv´an´ı z A na C (staˇc´ı prohodit oznaˇcen´ı kol´ık˚ u B a C), a proto kroky 1 a 3 vyˇzaduj´ı kaˇzd´ y Hn−1 tah˚ u. Krok 2 zvl´adneme v jednom tahu. D´ıky t´eto u ´vaze dosp´ıv´ame k rekurentn´ım rovnic´ım ( 1 pro n = 1 Hn = 2Hn−1 + 1 jinak. Na z´akladˇe tˇechto rovnic snadno dojdeme k explicitn´ımu vyj´adˇren´ı Hn . M˚ uˇzeme pouˇz´ıt substituci (viz [11]), a to tak ˇze nejdˇr´ıve k obˇema stran´am pˇriˇcteme jedniˇcku. Dost´av´ame H1 + 1 = 2 Hn + 1 = 2Hn−1 + 2 pro n > 1. Nyn´ı poloˇz´ıme Tn = Hn + 1, ˇcili T1 = 2 Tn = 2Tn−1

pro n > 1.

Odtud explicitnˇe vyj´adˇr´ıme Tn : Tn = 2 · Tn−1 = 2 · 2 · Tn−2 = . . . = 2| · .{z . . · 2} ·T1 = 2n . n − 1 dvojek

Protoˇze Hn = Tn − 1, dost´av´ame v´ ysledek Hn = 2n − 1 pro n ≥ 1.

(2.1)

Vr´at´ıme-li se k legendˇe z u ´vodu t´eto kapitoly, vid´ıme, ˇze pˇrenesen´ı 64 krouˇzk˚ u 64 . 19 vyˇzaduje 2 = 1,8 · 10 tah˚ u. Pˇri rychlosti jeden tah za vteˇrinu by cel´ y proces trval v´ıc neˇz 500 miliard let. Nyn´ı jsme se zab´ yvali pouze situac´ı, kdy jsou vˇsechny kotouˇce na poˇca´tku na jedin´em kol´ıku. M˚ uˇzeme se ale rozhodnout pˇresouvat kol´ıky z libovoln´eho poˇca´teˇcn´ıho stavu do libovoln´eho koncov´eho. Horn´ı odhad na poˇcet potˇrebn´ ych tah˚ u z´ısk´ame pomˇernˇe jednoduˇse. O tom uˇz u ´loha z [11]. ´ Uloha 11. Existuj´ı nˇejak´e dvˇe konfigurace n kotouˇc˚ u na tˇrech kol´ıc´ıch takov´e, ˇze n by pˇresun mezi nimi vyˇzadoval v´ıce neˇz 2 − 1 tah˚ u?

13

Odpovˇed’ zn´ı ne a dok´aˇzeme si ji indukc´ı. Pro n = 1 pˇresuneme kotouˇc odkudkoliv kamkoliv na nejv´ yˇse jeden tah, coˇz vyhovuje poˇzadavk˚ um. D´ale pˇredpokl´ad´ame, ˇze pˇresun mezi libovoln´ ymi k–kotouˇcov´ ymi konfiguracemi vyˇzaduje nanejv´ yˇs 2k − 1 tah˚ u, pro k = 1, . . . n − 1. Nyn´ı uvaˇzujme n kotouˇc˚ u. Pokud je nejvˇetˇs´ı kotouˇc v obou uspoˇra´d´an´ıch na stejn´em kol´ıku, v˚ ubec s n´ım nebudeme h´ ybat a zbyl´ ych n − 1 kotouˇc˚ u uspoˇra´d´ame bˇehem nejv´ yˇse 2n−1 − 1 ≤ 2n − 1 tah˚ u. Jinak m˚ uˇzeme postupovat n´asledovnˇe: 1. Pˇresuneme n − 1 nejmenˇs´ıch kotouˇc˚ u mimo poˇca´teˇcn´ı a c´ılov´ y kol´ık nejvˇetˇs´ıho kotouˇce. 2. Pˇresuneme nejvˇetˇs´ı kotouˇc na kol´ık, kter´ y vyˇzaduje koncov´a konfigurace. 3. Pˇresuneme n − 1 ostatn´ıch kotouˇc˚ u do poˇzadovan´eho uspoˇra´d´an´ı. ˇ adn´ Z´ y z krok˚ u 1 a 3 netrv´a d´ıky indukˇcn´ımu pˇredpokladu v´ıc neˇz 2n−1 − 1 tah˚ u. Celkem je tedy tˇreba nejv´ yˇse (2n−1 − 1) + 1 + (2n−1 − 1) = 2n − 1 tah˚ u. Uvˇedomme si, ˇze jsme z´aroveˇ n dok´azali i to, ˇze od libovoln´e konfigurace kotouˇc˚ u lze doj´ıt do libovoln´e jin´e.

2.2

ˇ sen´ı trochu jinak Reˇ

Vrat’me se jeˇstˇe k ˇreˇsen´ı hanojsk´ ych vˇeˇz´ı. Snadno si uvˇedom´ıme, ˇze optim´aln´ı posloupnost tah˚ u je jen jedna. S jej´ım rekurzivn´ım popisem si sice vystaˇc´ıme, ale je zaj´ımav´e pod´ıvat se na pohyby kotouˇc˚ u trochu podrobnˇeji jako napˇr. v [31]. Nejdˇr´ıv se zamysleme nad t´ım, ve kter´em tahu se pohybuje kter´ y kotouˇc, aniˇz bychom se zaj´ımali o to, mezi kter´ ymi kol´ıky tento tah prob´ıh´a. Nejjednoduˇsˇs´ı to je s nejvˇetˇs´ım kotouˇcem. Ten se pohne jednou, a to pˇresnˇe uprostˇred cel´e posloupnosti tah˚ u. Nav´ıc t´ım tuto posloupnost rozdˇel´ı na dva stejn´e u ´seky, z nichˇz kaˇzd´ y odpov´ıd´a pˇresunu n − 1 kotouˇc˚ u. Druh´ y nejvˇetˇs´ı kotouˇc se pohne vˇzdy pˇresnˇe uprostˇred tˇecho u ´sek˚ u a tak bychom mohli pokraˇcovat aˇz k nejmenˇs´ımu. Situaci pro n = 5 ilustruje obr. 2.2.

Obr´azek 2.2: Hanojsk´e vˇeˇze pro pˇet kotouˇc˚ u – d´elka ˇca´rky odpov´ıd´a velikosti toho pr´avˇe pˇresouvan´eho. Aby se n´am o kotouˇc´ıch l´epe mluvilo, oˇc´ıslujme si je od nejmenˇs´ıho podle velikosti 1, . . . , n. D´ıky obr´azku snadno pˇrijdeme na to, ˇze kotouˇc 1 je pˇresouv´an v kaˇzd´em lich´em tahu, kotouˇc 2 v kaˇzd´em sud´em tahu, jehoˇz ˇc´ıslo ale nen´ı dˇeliteln´e ˇctyˇrmi, . . . , i v tahu, jehoˇz ˇc´ıslo je dˇeliteln´e 2i−1 , ale ne 2i . (D˚ ukaz by bylo moˇzno prov´est napˇr. indukc´ı.) Toto zjiˇstˇen´ı lze pˇeknˇe interpretovat, zap´ıˇseme-li ˇc´ısla tah˚ u ve dvojkov´e soustavˇe. Tˇri kotouˇce vyˇzaduj´ı sedm tah˚ u. Kdy je kter´ ym taˇzeno pozn´ame n´asledovnˇe: 14

001 010 011 100 101 110 111

Pˇresouv´ame Pˇresouv´ame Pˇresouv´ame Pˇresouv´ame Pˇresouv´ame Pˇresouv´ame Pˇresouv´ame

kotouˇc 1. kotouˇc 2. kotouˇc 1. kotouˇc 3. kotouˇc 1. kotouˇc 2. kotouˇc 1.

V kaˇzd´em tahu pˇresouv´ame kotouˇc odpov´ıdaj´ıc´ı pozici posledn´ı jedniˇcky ve dvojkov´em z´apisu ˇc´ısla tohoto tahu. (Prvn´ı ˇc´ıslice odpov´ıd´a nejvˇetˇs´ımu kotouˇci, posledn´ı nejmenˇs´ımu.) Nyn´ı se zamˇeˇrme na to, odkud kam se kter´ y kotouˇc pˇresouv´a. Chceme-li nˇekomu pˇredv´est, jak um´ıme hlavolam ˇreˇsit, bude pro n´as kl´ıˇcov´e umˇet zodpovˇedˇet ot´azku, kam pˇresunout nejmenˇs´ı kotouˇc v prvn´ım tahu, je-li naˇs´ım c´ılem, aby vˇeˇz na konci st´ala na tˇret´ım kol´ıku. K tomu postaˇc´ı prost´a u ´vaha. Kotouˇc n budeme pˇresouvat pouze jednou, a to na kol´ık C. Aby to bylo moˇzn´e, mus´ı b´ yt na B pˇresunut kotouˇc n − 1. K tomu ale potˇrebujeme nejdˇr´ıv pˇresunout kotouˇc n − 2 na C atd. Vid´ıme, ˇze prvn´ı tah kotouˇce se stejnou paritou jako m´a n je na kol´ık C, s opaˇcnou paritou na kol´ık B. Pˇri lich´em poˇctu kotouˇc˚ u ten nejmenˇs´ı tedy v prvn´ım tahu pˇresuneme na C, pˇri sud´em poˇctu na B. D´ale m˚ uˇzeme vypozorovat, ˇze se kaˇzd´ y kotouˇc pohybuje bud’ pouze ve smˇeru A → B → C → A → . . ., nebo pouze ve smˇeru A → C → B → A → . . .. D˚ ukaz provedeme indukc´ı. Pro mal´e poˇcty kotouˇc˚ u tvrzen´ı snadno ovˇeˇr´ıme a d´ale pˇredpokl´ad´ame, ˇze plat´ı pro 1, 2, . . . , n − 1. Pro n kotouˇc˚ u pak nejdˇr´ıve pˇresuneme n − 1 kotouˇc˚ u z A na B. Z indukˇcn´ıho pˇredpokladu plyne, ˇze se kaˇzd´ y z nich bˇehem tohoto pˇresunu pohybuje pouze v jednom smˇeru. Pot´e pˇresuneme nejvˇetˇs´ı kotouˇc. Ten vykon´a jedin´ y tah, tvrzen´ı tedy splˇ nuje. Pot´e pˇresuneme n − 1 kotouˇc˚ u z B na C. M˚ uˇze se st´at, ˇze by se smˇer nˇekter´eho z nich obr´atil? Ne, protoˇze vˇeˇz z n − 1 kotouˇc˚ u byla v obou pˇr´ıpadech posunuta ve stejn´em smˇeru. Uvˇedomme si jeˇstˇe, ˇze pokud pr´avˇe nehodl´ame pˇresunout nejmenˇs´ı kotouˇc, je v kaˇzd´e pozici (vyjma poˇca´teˇcn´ı a koncov´e) pr´avˇe jeden dalˇs´ı pˇr´ıpustn´ y tah. Z v´ yˇse uveden´ ych poznatk˚ u v´ıme, ˇze nejmenˇs´ım kotouˇcem je h´ yb´ano v kaˇzd´em lich´em tahu, a to pouze v jednom smˇeru, kter´ y z´aleˇz´ı na paritˇe n. Cel´ y algoritmus tedy spoˇc´ıv´a v opakov´an´ı n´asleduj´ıc´ı dvou krok˚ u, dokud nen´ı cel´a vˇeˇz pˇresunuta na C: 1. Pˇresuneme nejmenˇs´ı kotouˇc v patˇriˇcn´em smˇeru (pro lich´e n proti, pro sud´e n po smˇeru hodinov´ ych ruˇciˇcek). 2. Pˇresuneme jin´ y neˇz nejmenˇs´ı kotouˇc (jedin´a moˇznost). Tento postup m˚ uˇzeme popsat i jinak, kdyˇz zamˇeˇr´ıme pozornost na to, mezi kter´ ymi kol´ıky k pˇresun˚ um doch´az´ı. Pro lich´e n (pro sud´e analogicky, zamˇenˇen´ım B a C) se opakuje n´asleduj´ıc´ı: 1. Tah z A na C (pˇresun nejmenˇs´ıho kotouˇce). 15

2. Pˇr´ıpustn´ y tah mezi A a B. 3. Tah z C na B. 4. Pˇr´ıpustn´ y tah mezi A a C. 5. Tah z B na A. 6. Pˇr´ıpustn´ y tah mezi B a C. Pod´ıv´ame-li se pozornˇeji, zjist´ıme, ˇze ve skuteˇcnosti se opakuj´ı pouze tˇri kroky: 1. Tah mezi A a C. 2. Tah mezi A a B. 3. Tah mezi B a C.

2.3

Pˇ r´ıˇ serky a koule

V [18] je uvedeno, ˇze se hanojsk´e vˇeˇze vyuˇz´ıvaj´ı ke zkoum´an´ı toho, jak lid´e ˇreˇs´ı probl´emy. Vyˇreˇsen´ı n´asleduj´ıc´ı u ´lohy pr´ y trv´a v pr˚ umˇeru ˇsestn´actkr´at d´ele neˇz vyˇreˇsen´ı j´ı izomorfn´ı u ´lohy zadan´e v pojmech hanojsk´ ych vˇeˇz´ı. Tˇri pˇr´ıˇsery drˇz´ı tˇri koule. Jak pˇr´ıˇsery, tak koule jsou ve tˇrech velikostech: mal´a, stˇredn´ı, velk´a. Mal´a pˇr´ıˇsera drˇz´ı velkou kouli, stˇredn´ı pˇr´ıˇsera drˇz´ı malou kouli a velk´a pˇr´ıˇsera drˇz´ı stˇrednˇe velkou kouli. Toto uspoˇr´ad´an´ı vˇsak ur´aˇz´ı smysl pˇr´ıˇser pro symetrii, a tak by chtˇely situaci zmˇenit do stavu, kdy kaˇzd´a pˇr´ıˇsera bude drˇzet kouli sv´e velikosti. Pˇr´ıˇsery mohou mˇenit velikost koul´ı, ale mus´ı pˇri tom dodrˇzovat pravidla etikety pˇr´ıˇser: • Vˇzdy se m˚ uˇze mˇenit velikost pouze jedn´e koule. • Pokud dvˇe pˇr´ıˇsery drˇz´ı koule stejn´e velikosti, jen koule, kterou drˇz´ı vˇetˇs´ı pˇr´ıˇsera, se m˚ uˇze zmˇenit. • Koule se nikdy nesm´ı zmˇenit na stejnou velikost jako koule, kterou drˇz´ı vˇetˇs´ı pˇr´ıˇsera. ´ Uloha 12. Jak´ym zp˚ usobem doc´ıl´ı pˇr´ıˇserky co nejrychleji stavu spokojenosti? ˇ sen´ı se v [18] neuv´ad´ı, ale nen´ı obt´ıˇzn´e na nˇej pˇrij´ıt. Zaˇcnou-li pˇr´ıˇserky Reˇ velikosti koul´ı bez d˚ ukladn´eho pˇrem´ yˇslen´ı (avˇsak za dodrˇzen´ı pravidel) mˇenit, nejsp´ıˇs se brzy dostanou do k´ yˇzen´eho stavu, protoˇze moˇznost´ı nen´ı mnoho, ale pravdˇepodobnˇe to nebude optim´aln´ım zp˚ usobem. Zapoj´ı-li rozum, povˇsimnou si, ˇze nejv´ıc diskriminov´ana“ je nejmenˇs´ı pˇr´ıˇserka. ” Ta m˚ uˇze zmˇenit svoji kouli na malou jen ve chv´ıli, kdy ˇza´dn´a z ostatn´ıch pˇr´ıˇser nedrˇz´ı malou kouli a ani kouli stejn´e velikosti, jako drˇz´ı mal´a pˇr´ıˇserka. V dan´e situaci to znamen´a, ˇze potˇrebuje, aby druh´e dvˇe pˇr´ıˇsery drˇzely stˇredn´ı koule. Jak toho doc´ılit, kdyˇz stˇredn´ı kouli drˇz´ı velk´a pˇr´ıˇsera, ale stˇredn´ı nikoliv? Velk´a pˇr´ıˇsera mus´ı t´e stˇredn´ı udˇelat prostor, a to t´ım, ˇze svoji kouli zmˇen´ı na takovou velikost, aby stˇredn´ı pˇr´ıˇseru neblokovala“, tj. na velkou. Pˇr´ıˇserky budou ” mˇenit koule t´ımto zp˚ usobem: V M S → V M V → V SV → V SS → M SS → M SV, 16

kde M , S a V postupnˇe znaˇc´ı malou, stˇredn´ı a velkou kouli a na prvn´ım m´ıstˇe je uvedena koule, kterou drˇz´ı mal´a, na druh´em stˇredn´ı a na tˇret´ım velk´a pˇr´ıˇsera. V SM tedy znaˇc´ı poˇca´teˇcn´ı stav koul´ı, jak je uveden v zad´an´ı u ´lohy, a M SV koneˇcn´ y stav, kdy kaˇzd´a pˇr´ıˇsera drˇz´ı kouli odpov´ıdaj´ıc´ı jej´ı velikosti. N´azornˇe je vˇse uk´az´ano na obr. 2.3. Toto pˇetikrokov´e ˇreˇsen´ı je nejlepˇs´ı moˇzn´e. Pro pˇr´ıpad, ˇze mal´a pˇr´ıˇserka mˇen´ı kouli pouze jednou bˇehem cel´eho procesu, ˇza´dn´e vylepˇsen´ı zˇrejmˇe nenajdeme. A moˇznost, kdy mˇen´ı kouli dvakr´at, nejprve na stˇredn´ı a pak teprve na malou, je mnohem zdlouhavˇejˇs´ı, dev´ıtikrokov´a: V M S → V M M → SM M → SM S → SV S → →SV V → M V V → M V M → M SM → M SV.

ˇ sen´ı u Obr´azek 2.3: Reˇ ´lohy o pˇr´ıˇserk´ach. Kdyˇz uˇz v´ıme, jak si se sv´ ym probl´emem porad´ı pˇr´ıˇserky, zkusme jeˇstˇe prozkoumat, jak vlastnˇe tato u ´loha souvis´ı s hanojsk´ ymi vˇeˇzemi. ´ Uloha 13. Najdˇete souvislost mezi hanojsk´ymi vˇeˇzemi a pˇr´ıˇserkami. Nejdˇr´ıve n´as m˚ uˇze napadnout ztotoˇznit kol´ıky s pˇr´ıˇserkami, nebot’ se jedn´a o statick´e objekty, kter´e se nemˇen´ı, a n´asledovnˇe kotouˇce s koulemi. Brzy ale zjist´ıme, ˇze tudy cesta nevede. Vˇzdyt’ napˇr´ıklad na kol´ıku m˚ uˇze b´ yt vˇetˇs´ı poˇcet kotouˇc˚ u, ale kaˇzd´a pˇr´ıˇserka drˇz´ı vˇzdy pr´avˇe jednu kouli. Zkusme tedy pˇrem´ yˇslet d´al. Na kotouˇc´ıch m´ame uspoˇra´d´an´ı dle velikosti. V druh´e u ´loze je toto uspoˇr´ad´an´ı na pˇr´ıˇserk´ach i koul´ıch, ale co se t´ yˇce pravidel, m´a opodstatnˇen´ı pouze pro pˇr´ıˇserky. V pˇr´ıpadˇe koul´ı slouˇz´ı pouze k pops´an´ı v´ ychoz´ı a c´ılov´e pozice, na coˇz by stejnˇe dobˇre staˇcilo napˇr. i to, kdyby se koule liˇsily v barvˇe, nikoli ve velikosti. Budeme proto kotouˇce ztotoˇzn ˇovat s pˇr´ıˇserkami a kol´ıky s koulemi. Konkr´etnˇe je to tak, ˇze ve hˇre m´ame 3 kotouˇce, pˇriˇcemˇz nejvˇetˇs´ı kotouˇc odpov´ıd´a nejmenˇs´ı pˇr´ıˇserce a naopak. Promˇena koule pˇr´ıˇserkou tak odpov´ıd´a pˇresunu kotouˇce pˇr´ısluˇsej´ıc´ıho dan´e pˇr´ıˇserce. Pravidla etikety pˇr´ıˇser pak lze pˇrepsat jako: 17

• Vˇzdy se m˚ uˇze pˇresouvat pouze jeden kotouˇc. (Protoˇze prvn´ı pravidlo vlastnˇe ˇr´ık´a, ˇze zmˇenu koule m˚ uˇze vˇzdy prov´adˇet pouze jedna pˇr´ıˇserka.) • Pokud je na kol´ıku v´ıce kotouˇc˚ u, jen nejmenˇs´ı kotouˇc m˚ uˇze b´ yt pˇresunut. • Vˇetˇs´ı kotouˇc se nesm´ı pˇresunout na kol´ık, kde je menˇs´ı kotouˇc. A vid´ıme, ˇze se jedn´a o pravidla hanojsk´ ych vˇeˇz´ı. Ztotoˇzn´ıme-li nejmenˇs´ı kouli s prvn´ım kol´ıkem a nejvˇetˇs´ı se tˇret´ım, ˇreˇs´ıme u ´lohu pomoc´ı hanojsk´ ych vˇeˇz´ı tak, jak je uvedeno na obr´azku 2.4.

ˇ sen´ı u Obr´azek 2.4: Reˇ ´lohy o pˇr´ıˇserk´ach v jazyce“ hanojsk´ ych vˇeˇz´ı. ”

2.4

Pozmˇ enˇ en´ a zad´ an´ı

´ Ulohy v t´eto sekci poch´azej´ı z [11]. ´ Uloha 14. Najdˇete nejkratˇs´ı posloupnost tah˚ u, kterou lze pˇresunout vˇeˇz o n kotouˇc´ıch z kol´ıku A na kol´ık C, jestliˇze pˇr´ım´e tahy mezi A a C jsou zak´az´any. Poˇcet potˇrebn´ ych tah˚ u pro n kotouˇc˚ u oznaˇc´ıme Gn . Pro n = 1 potˇrebujeme dva tahy (z A na B a z B na C). Pro vˇetˇs´ı n si opˇet poloˇzme onu kl´ıˇcovou ot´azku: Jak bude pˇresunut nejvˇetˇs´ı kotouˇc? Zˇrejmˇe nejdˇr´ıve z A na B, pˇriˇcemˇz ostatn´ıch n − 1 kotouˇc˚ u mus´ı b´ yt na C, a pot´e z B na C ve chv´ıli, kdy jsou ostatn´ı kotouˇce na A. Cel´ y postup tak m˚ uˇzeme zapsat jako: 1. Pˇresuneme n − 1 vrchn´ıch kotouˇc˚ u z A na C. 2. Pˇresuneme nejvˇetˇs´ı kotouˇc z A na B. 3. Pˇresuneme n − 1 kotouˇc˚ u z C na A. 4. Pˇresuneme nejvˇetˇs´ı kotouˇc z B na C. 5. Pˇresuneme n − 1 kotouˇc˚ u z A na C. Pro kol´ıky A a C z˚ ust´av´a u ´loha symetrick´a, ˇcili pˇresun z A na C je stejnˇe n´aroˇcn´ y jako z C na A. Kaˇzd´ y z krok˚ u 1, 3 a 5 tedy vyˇzaduje Gn−1 tah˚ u. Dost´av´ame tak rekurentn´ı rovnice ( 2 pro n = 1 Gn = 3Gn−1 + 2 jinak. Explicitn´ı vyj´adˇren´ı Gn je pak Gn = 3n − 1 pro n ≥ 1. 18

Dalo by se k nˇemu dospˇet jiˇz dˇr´ıve zm´ınˇenou substituˇcn´ı metodou. Jeho platnost m˚ uˇzeme dok´azat za pomoci matematick´e indukce. Pro n = 1 vztah plat´ı a pˇredpokl´ad´ame-li, ˇze plat´ı pro 1, . . . , n − 1, dost´av´ame Gn = 3Gn−1 + 2 = 3(3n−1 − 1) + 2 = 3n − 1. ´ Uloha 15. Ukaˇzte, ˇze v pr˚ ubˇehu ˇreˇsen´ı pˇredchoz´ı u ´lohy se vyskytnou vˇsechna pˇr´ıpustn´a uspoˇr´ad´an´ı kotouˇc˚ u na kol´ıc´ıch. Je dobr´e si uvˇedomit, ˇze informace o tom, kter´ y kotouˇc leˇz´ı na kter´em kol´ıku, ’ jiˇz jednoznaˇcnˇe ud´av´a jejich uspoˇr´ad´an´ı, nebot kotouˇce na kol´ıku jsou vˇzdy v poˇrad´ı od nejvˇetˇs´ıho po nejmenˇs´ı. Pro kaˇzd´ y z n kotouˇc˚ u jsou 3 moˇznosti, kde se m˚ uˇze vyskytovat. Vˇsech pˇr´ıpustn´ ych uspoˇr´ad´an´ı je tedy 3n . n ˇ sen´ı pˇredchoz´ı u Reˇ ´lohy vyˇzadovalo 3 − 1 tah˚ u, ˇcili se bˇehem nˇej vyskytlo 3n uspoˇra´d´an´ı. Ta jsou jistˇe po dvou r˚ uzn´a, protoˇze ˇreˇsen´ı bylo optim´aln´ı. Pokud by totiˇz nˇejak´a dvˇe byla stejn´a, dala by se posloupnost tah˚ u zkr´atit o cel´ yu ´sek mezi nimi. Odtud jiˇz vid´ıme, ˇze se opravdu vyskytla vˇsechna moˇzn´a uspoˇr´ad´an´ı. ´ Uloha 16. Uvaˇzujme variantu hanojsk´ych vˇeˇz´ı, kde jsou povoleny pouze tahy ve smˇeru hodinov´ych ruˇciˇcek, tj. z A na B, z B na C a z C na A. Na kol´ıku A je vˇeˇz z n kotouˇc˚ u. Kolik tah˚ u je tˇreba na jejich pˇresunut´ı na kol´ık B, resp. na kol´ık C? Poˇcet tah˚ u potˇrebn´ ych pro pˇresun n kotouˇc˚ u o jeden kol´ık po smˇeru hodinov´ ych ruˇciˇcek oznaˇc´ıme Qn , proti smˇeru Rn . Zˇrejmˇe Q1 = 1 a R1 = 2. Chceme-li pˇresunout n kotouˇc˚ u z A na B, postupujeme n´asledovnˇe: 1. Pˇresuneme n − 1 vrchn´ıch kotouˇc˚ u z A na C, coˇz vyˇzaduje Rn−1 tah˚ u. 2. Pˇresuneme nejvˇetˇs´ı kotouˇc z A na B (1 tah). 3. Pˇresuneme n − 1 kotouˇc˚ u z C na B (Rn−1 tah˚ u). Pˇresun n kotouˇc˚ u z A na C provedeme takto: 1. Pˇresuneme n − 1 vrchn´ıch kotouˇc˚ u z A na C (Rn−1 tah˚ u). 2. Pˇresuneme nejvˇetˇs´ı kotouˇc z A na B (1 tah). 3. Pˇresuneme n − 1 kotouˇc˚ u z C na A (Qn−1 tah˚ u). 4. Pˇresuneme nejvˇetˇs´ı kotouˇc z B na C (1 tah). 5. Pˇresuneme n − 1 kotouˇc˚ u z A na C (Rn−1 tah˚ u). Dost´av´ame tak soustavu rekurentn´ıch rovnic: Qn Rn Q1 R1

= 2Rn−1 + 1 pro n > 1 = 2Rn−1 + Qn−1 + 2 pro n > 1 =1 = 2.

Abychom z´ıskali explicitn´ı vyj´adˇren´ı Qn a Rn , rovnice jeˇstˇe m´ırnˇe uprav´ıme: Rn = 2Rn−1 + Qn−1 + 2 = 2Rn−1 + 2Rn−2 + 3 = 2Rn−1 + 1 + Qn−1 + 1 = Qn + Qn−1 + 1 Qn = 2Rn−1 + 1 = 2Qn−1 + 2Qn−2 + 3. 19

(2.2) (2.3) (2.4)

Vztah (2.3) jsme vyuˇzili pro odvozen´ı (2.4). Dopoˇc´ıt´ame-li jeˇstˇe Q2 = 5 a R2 = 7, m˚ uˇzeme nahl´ıˇzet na (2.2) a (2.4) jako na samostatn´e rekurentn´ı rovnice. Obecn´ y zp˚ usob jejich ˇreˇsen´ı je moˇzno naj´ıt napˇr. v [5]. My si zde uvedeme pouze v´ ysledek, ten by se dal dok´azat pomoc´ı indukce:  √ √ 1  Qn = √ (1 + 3)n+1 − (1 − 3)n+1 − 1 pro n ≥ 1 2 3 √ n+2 √ n+2  1  Rn = √ (1 + 3) − (1 − 3) − 1 pro n ≥ 1. 4 3 ´ Uloha 17. Pˇredpokl´adejme, ˇze m´ame n dvojic stejnˇe velk´ych kotouˇc˚ u, vˇzdy b´ıl´y a ˇcern´y, kter´e jsou na poˇc´atku uspoˇr´ad´any na kol´ıku A, a to tak, ˇze na ˇcern´em vˇzdy leˇz´ı b´ıl´y stejn´e velikosti. St´ale plat´ı pravidlo, ˇze vˇetˇs´ı kotouˇc nesm´ıme poloˇzit na menˇs´ı. Stejnˇe velk´e na sebe m˚ uˇzeme pokl´adat libovolnˇe. Na kolik nejm´enˇe tah˚ u je dok´aˇzeme pˇrem´ıstit na kol´ık C tak, aby na konci opˇet na kaˇzd´em ˇcern´em kotouˇci leˇzel b´ıl´y stejn´e velikosti? Nejdˇr´ıv uvaˇzme situaci, kdy n´am nez´aleˇz´ı na uspoˇra´d´an´ı ˇcern´ ych a b´ıl´ ych a pouze chceme pˇresunout vˇeˇz z A na C. Oznaˇcme Gn poˇcet potˇrebn´ ych tah˚ u pro 2n kotouˇc˚ u. Jak budeme postupovat? Zˇrejmˇe u ´plnˇe stejnˇe jako v pˇr´ıpadˇe z´akladn´ı varianty hanojsk´ ych vˇeˇz´ı, jenom by se dalo ˇr´ıct, ˇze kaˇzd´ y tah provedeme dvakr´at, kotouˇce stejn´e velikosti budeme nech´avat pˇri sobˇe. Odtud Gn = 2Hn = 2 · (2n − 1) = 2n+1 − 2. Nyn´ı uˇz pˇredpokl´adejme, ˇze chceme zachovat uspoˇra´d´an´ı ˇcern´a – b´ıl´a. Poˇcet tah˚ u pro n dvojic oznaˇc´ıme Fn . Zamysleme se, jestli Fn = Gn . Bohuˇzel nikoliv. Dvojice nejvˇetˇs´ıch kotouˇc˚ u se totiˇz pˇresunuje pouze jednou, z A na C, pˇriˇcemˇz je nejdˇr´ıv pˇresunut b´ıl´ y kotouˇc a potom teprve ˇcern´ y, kter´ y se tak ocitne na b´ıl´em. Tady si uvˇedom´ıme, ˇze chceme-li dvojici kotouˇc˚ u drˇzet neust´ale pˇri sobˇe, mus´ı b´ yt poˇcet jejich pˇrem´ıstˇen´ı sud´ y, po lich´em poˇctu pˇrem´ıstˇen´ı skonˇc´ı ˇcern´ y kotouˇc na b´ıl´em. Jenom podotkneme, ˇze F1 = 3. Pro n > 1, jak se n´am doposud osvˇedˇcilo, zaˇcneme s ˇreˇsen´ım probl´emu od nejspodnˇejˇs´ı dvojice kotouˇc˚ u. Nab´ız´ı se dva postupy. Prvn´ı z nich se zab´ yv´a myˇslenkou pˇresunout tuto dvojici dvakr´at: 1. Pˇresuneme standardnˇe n − 1 vrchn´ıch dvojic z A na C. 2. Pˇresuneme nejvˇetˇs´ı kotouˇce z A na B. 3. Pˇresuneme standardnˇe n − 1 dvojic z C na A. 4. Pˇresuneme nejvˇetˇs´ı kotouˇce z B na C. 5. Pˇresuneme nadstandardnˇe n − 1 dvojic z A na C. Pojmem standardnˇe“ zde rozum´ıme pˇresun nezohledˇ nuj´ıc´ı uspoˇra´d´an´ı ˇcern´a – ” b´ıl´a a pojmem nadstandardnˇe“ ten, kter´ y je zohledˇ nuje. Kaˇzd´ y z krok˚ u1a3 ” tedy vyˇzaduje Gn−1 tah˚ u a 5. krok Fn−1 tah˚ u. Zde si mus´ıme uvˇedomit, ˇze kroky 1 a 3 zaruˇcuj´ı, ˇze kaˇzd´a z n − 1 dvojic kotouˇc˚ u absolvovala sud´ y poˇcet pˇresun˚ u (stejnˇe v prvn´ım jako ve tˇret´ım kroku), a tedy na poˇc´atku kroku 5 jsou kotouˇce

20

v z´akladn´ım uspoˇra´d´an´ı, ˇcili se probl´em zredukoval na u ´lohu pro n − 1 dvojic. Kroky 2 a 4 jsou kaˇzd´ y na dva tahy. Odtud dost´av´ame Fn = Fn−1 + 2Gn−1 + 4 = Fn−1 + 2 · (2n − 2) + 4 = Fn−1 + 2n+1 = = Fn−2 + 2n + 2n+1 = . . . = F1 + 23 + 24 + . . . + 2n+1 = 3 + 2n+2 − 8 = = 2n+2 − 5. Tento v´ ysledek pro Fn je optim´aln´ı pouze za pˇredpokladu, ˇze n´asleduj´ıc´ı ˇreˇsen´ı nenab´ıdne lepˇs´ı. Mus´ıme totiˇz jeˇstˇe provˇeˇrit druh´ y n´apad, a to pˇresunout nejvˇetˇs´ı b´ıl´ y kotouˇc z A na B, potom nejvˇetˇs´ı ˇcern´ y z A na C a pak nejvˇetˇs´ı b´ıl´ y z B na C (stejn´ y postup vlastnˇe pouˇz´ıv´ame, ˇreˇs´ıme-li u ´lohu pouze pro jedinou dvojici kotouˇc˚ u). Cel´ y proces prob´ıh´a takto: 1. Pˇresuneme standardnˇe n − 1 vrchn´ıch dvojic z A na C. 2. Pˇresuneme nejvˇetˇs´ı b´ıl´ y kotouˇc z A na B. 3. Pˇresuneme standardnˇe n − 1 dvojic z C na B. 4. Pˇresuneme nejvˇetˇs´ı ˇcern´ y kotouˇc z A na C. 5. Pˇresuneme standardnˇe n − 1 dvojic z B na C. 6. Pˇresuneme nejvˇetˇs´ı b´ıl´ y kotouˇc z B na C. 7. Pˇresuneme standardnˇe n − 1 dvojic z C na A. Protoˇze standardn´ıch pˇresun˚ u probˇehl sud´ y poˇcet, m˚ uˇzeme si b´ yt jisti spr´avn´ ym koneˇcn´ ym uspoˇr´ad´an´ım. Lich´e kroky zabraly kaˇzd´ y Gn−1 tah˚ u a sud´e kroky kaˇzd´ y po jednom tahu. Celkovˇe tedy dost´av´ame Fn = 4Gn−1 + 3 = 4 · (2n − 2) + 3 = 2n+2 − 5. Dospˇeli jsme, moˇzn´a trochu pˇrekvapivˇe, ke stejn´emu v´ ysledku jako v pˇredchoz´ım postupu. To znamen´a, ˇze pro n ≥ 2 existuje v´ıce neˇz jedna optim´aln´ı sekvence tah˚ u. M˚ uˇzeme pouˇz´ıvat prvn´ı postup a kdykoliv, kdyˇz jsou vˇetˇs´ı kotouˇce na C a menˇs´ı na A, nejpozdˇeji vˇsak ve chv´ıli, kdy na A zb´ yv´a jen nejmenˇs´ı dvojice kotouˇc˚ u, pˇrej´ıt k druh´emu postupu.

2.5

Hanojsk´ e vˇ eˇ ze na ˇ ctyˇ rech kol´ıc´ıch

Doposud jsme vˇzdy pˇredpokl´adali, ˇze n´aˇs hlavolam m´a pr´avˇe 3 kol´ıky. Ale jak se n´aˇs probl´em zmˇen´ı, pˇrid´ame-li kol´ıky dalˇs´ı? Zˇrejmˇe uˇz nebude potˇreba tolik tah˚ u pro pˇresun vˇeˇze, ale zt´ıˇz´ı se hled´an´ı optim´aln´ıho ˇreˇsen´ı. My se zde omez´ıme pouze na ˇctyˇri kol´ıky, nebot’ tento pˇr´ıpad je s´am o sobˇe dostateˇcnˇe zaj´ımav´ y i n´azorn´ y. Zbytek t´eto kapitoly vych´az´ı z poznatk˚ u obsaˇzen´ ych v [10] a [29], kde ˇcten´aˇr nalezne v´ıce podrobnost´ı, napˇr. i zobecnˇen´ı z´akladn´ı varianty pro libovoln´ y poˇcet kol´ık˚ u. ´ Uloha 18. Uvaˇzujme variantu hanojsk´ych vˇeˇz´ı, kde jsou ˇctyˇri kol´ıky, oznaˇcme je A aˇz D. Jak´y je nejmenˇs´ı poˇcet tah˚ u potˇrebn´ych pro pˇresun vˇeˇze o n kotouˇc´ıch z A na D?

21

Hned v u ´vodu je nutno poznamenat, ˇze tento probl´em z˚ ust´av´a doposud otevˇren´ y. Za optim´aln´ı se povaˇzuje n´asleduj´ıc´ı Frame-Stewart˚ uv algoritmus, jeho optimalitu se vˇsak nepodaˇrilo dok´azat. 1. Rekurzivnˇe (s pouˇzit´ım vˇsech kol´ık˚ u) pˇrem´ıst´ıme n − i nejmenˇs´ıch kotouˇc˚ u z A na B. 2. Pˇresuneme i nejvˇetˇs´ıch kotouˇc˚ u z A na D, pˇriˇcemˇz ignorujeme kol´ık B. 3. Rekurzivnˇe pˇrem´ıst´ıme n − i kotouˇc˚ u z B na D. Druh´ y krok odpov´ıd´a klasick´ ym hanojsk´ ym vˇeˇz´ım s i kotouˇci, vyˇzaduje tedy 2 − 1 tah˚ u, viz (2.1). Kl´ıˇcov´a je volba i, kter´e vol´ıme tak, aby v´ ysledn´ y poˇcet tah˚ u byl minim´aln´ı. Oznaˇc´ıme-li jako Gn nejmenˇs´ı poˇcet tah˚ u potˇrebn´ ych pro pˇresun n kotouˇc˚ u za pomoci ˇctyˇr kol´ık˚ u (pˇri pouˇzit´ı Frame-Stewartova algoritmu), dost´av´ame i

Gn = min (2Gn−i + 2i − 1) 1≤i≤n

G1 = 1. V [29] je odtud odvozeno explicitn´ı vyj´adˇren´ı pro Gn . Prozrad´ıme si v´ ysledek: √ Gn = 2s−2 (2n − s2 + 3s − 4) + 1, kde s = { 2n}∗ Pro porovn´an´ı s klasick´ ymi hanojsk´ ymi vˇeˇzemi se pod´ıvejme, jak by si vedli knˇeˇz´ı v Ban´arasu, kdyby√pro pˇresun 64 kotouˇc˚ u mohli m´ısto tˇr´ı kol´ık˚ u pouˇz´ıvat ˇctyˇri. Dost´av´ame s = { 128} = 11 a G64 = 18433. Znamen´a to, ˇze i kdyby knˇeˇz´ı pˇresunuli jeden kotouˇc dennˇe, nam´ısto kaˇzdou vteˇrinu, skonˇcil by svˇet po pˇribliˇznˇe pades´ati letech. ˇ anek [29] se zab´ Cl´ yv´a i dalˇs´ımi variantami hanojsk´ ych vˇeˇz´ı na ˇctyˇrech kol´ıc´ıch. Pro situace, kdy jsou povoleny pouze tahy po smˇeru hodinov´ ych ruˇciˇcek nebo jenom mezi sousedn´ımi kol´ıky, uv´ad´ı, ˇze dosud nen´ı zn´am ˇza´dn´ y efektivn´ı algoritmus vedouc´ı k nalezen´ı optim´aln´ıch ˇreˇsen´ı. Zjednoduˇsenˇe ˇreˇceno je tˇreba vyzkouˇset vˇsechny moˇznosti a vybrat z nich tu nejlepˇs´ı. Nav´ıc pro menˇs´ı hodnoty n bylo zjiˇstˇeno, ˇze r˚ uzn´ ych optim´aln´ıch posloupnost´ı tah˚ u existuje velk´e mnoˇzstv´ı, coˇz v z´asadˇe potvrzuje, ˇze se jedn´a o komplikovan´ y probl´em. D´ale vˇsak autor uv´ad´ı variantu, kdy jsou kol´ıky uspoˇr´ad´any jako hvˇezda. Pro ni existuje pˇekn´e ˇreˇsen´ı, aˇckoliv jeho optimalita, podobnˇe jako v pˇredchoz´ı u ´loze, nen´ı dok´az´ana. Spoleˇcnˇe se na ni nyn´ı pod´ıvejme. ´ Uloha 19. Uvaˇzujme variantu hanojsk´ych vˇeˇz´ı na ˇctyˇrech kol´ıc´ıch, kdy kaˇzd´y tah mus´ı v´est z nebo na kol´ık B (kol´ık B si m˚ uˇzeme pˇredstavit jako stˇred hvˇezdy, ostatn´ı jako jej´ı c´ıpy). Naˇs´ım u ´kolem je pˇresunout vˇeˇz o n kotouˇc´ıch z A na D. Na kolik nejm´enˇe tah˚ u je to moˇzn´e? Pouˇzijeme algoritmus podobn´ y Frame-Stewartovu: 1. Rekurzivnˇe (s pouˇzit´ım vˇsech kol´ık˚ u) pˇrem´ıst´ıme n − i nejmenˇs´ıch kotouˇc˚ u z A na C. 2. Pˇresuneme i nejvˇetˇs´ıch kotouˇc˚ u z A na D, pˇriˇcemˇz nevyuˇz´ıv´ame kol´ık C. ∗

{x} znaˇc´ı nejbliˇzˇs´ı cel´e ˇc´ıslo k ˇc´ıslu x.

22

3. Rekurzivnˇe pˇrem´ıst´ıme n − i kotouˇc˚ u z C na D. V tomto pˇr´ıpadˇe odpov´ıd´a krok 2 u ´loze 14, vyˇzaduje tedy 3i − 1 tah˚ u. Oznaˇc´ıme-li Sn nejmenˇs´ı poˇcet tah˚ u potˇrebn´ ych k pˇrenesen´ı n kotouˇc˚ u z A na D za pomoci tohoto algoritmu, dost´av´ame Sn = min (2Sn−i + 3i − 1) 1≤i≤n

S1 = 2. Explicitn´ı vyj´adˇren´ı pro Sn bohuˇzel nem´ame, ale [29] uv´ad´ı v´ ysledek, kter´ y ’ lze k v´ ypoˇctu Sn vyuˇz´ıt. Necht {am }∞ m=1 = (1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, . . .) je posloupnost ˇc´ısel 2j 3k , j, k ≥ 0, uspoˇr´adan´ ych v rostouc´ım poˇrad´ı. Pak tvrd´ıme, ˇze n X Sn = 2 am . (2.5) m=1

Staˇc´ı n´am uk´azat, ˇze vˇzdy pr´avˇe jeden z n kotouˇc˚ u vykon´a pr´avˇe 2am tah˚ u pro m = 1, 2, . . . , n, z ˇcehoˇz uˇz pˇr´ımo plyne (2.5). K d˚ ukazu pouˇzijeme indukci. Pro mal´e hodnoty n nen´ı probl´em toto tvrzen´ı ovˇeˇrit. Pˇredpokl´adejme nyn´ı, ˇze plat´ı pro 1, 2, . . . , n − 1. Uk´aˇzeme, ˇze plat´ı i pro n. Nejdˇr´ıv si uvˇedom´ıme, ˇze j-t´ y nejvˇetˇs´ı kotouˇc z kroku 2, tj. pˇresouvan´ y bez j−1 vyuˇzit´ı kol´ıku C, vykon´a 2 · 3 tah˚ u. (To m˚ uˇzeme uk´azat indukc´ı. Nejvˇetˇs´ı kotouˇc vykon´a 2 tahy, takˇze pro nˇej tvrzen´ı plat´ı. D´ale pˇredpokl´adejme, ˇze plat´ı pro vˇsechny aˇz vˇcetnˇe (j − 1)-n´ıho nejvˇetˇs´ıho kotouˇce. Uk´aˇzeme, ˇze plat´ı i pro j-t´ y. Pˇrid´an´ım j-t´eho kotouˇce se poˇcty tah˚ u ostatn´ıch nezmˇen´ı. Zat´ımco j − 1 j−1 kotouˇc˚ u se pˇresunulo pomoc´ı celkem 3 − 1 tah˚ u, j kotouˇc˚ u jich potˇrebovalo j j j−1 3 − 1. Na j-t´ y kotouˇc jich tedy pˇripad´a (3 − 1) − (3 − 1) = 2 · 3j−1 .) To 0 1 znamen´a, ˇze i kotouˇc˚ u z kroku 2 vykon´a 2 · 3 , 2 · 3 , . . . , 2 · 3i−1 tah˚ u. Ostatn´ıch n − i kotouˇc˚ u je dvakr´at rekurzivnˇe pˇresouv´ano, podle indukˇcn´ıho pˇredpokladu tedy vykon´a 4a1 , 4a2 , . . . , 4an−i tah˚ u. Vid´ıme, ˇze ˇza´dn´e dva kotouˇce nevykonaj´ı stejn´ y poˇcet tah˚ u, protoˇze poˇcet tah˚ u kaˇzd´eho z n−i menˇs´ıch kotouˇc˚ u je n´asobkem ˇctyˇrky, zat´ımco poˇcet tah˚ u i vˇetˇs´ıch kotouˇc˚ u nikoli. Hled´ame i tak, aby souˇcet prvnk˚ u z {2·30 , 2·31 , . . . , 2·3i−1 }∪{4a1 , 4a2 , . . . , 4an−i } byl minim´aln´ı. Tj. chceme minimalizovat souˇcet prvk˚ uz M = {30 , 31 , . . . , 3i−1 } ∪ {2a1 , 2a2 , . . . , 2an−i }. Zˇrejmˇe M ⊂ {a1 , a2 , a3 , . . .} Protoˇze {am }∞ ı, bude souˇcet urˇcitˇe m=1 je rostouc´ minim´aln´ı, pokud M = {a1 , . . . , an }. (2.6) Poloˇzme si ot´azku, zda existuje i takov´e, aby platilo (2.6). Odpovˇed’ zn´ı ano. Za i zvol´ıme poˇcet prvk˚ u v {a1 , . . . , an }, kter´e lze zapsat jako 3k , k ≥ 0. Tyto prvky odpov´ıdaj´ı pr´avˇe hodnot´am 30 , 31 , . . . , 3i−1 . Zb´ yvaj´ıc´ıch n − i hodnot j k z {a1 , . . . , an } lze ps´at ve tvaru 2 3 , j ≥ 1, k ≥ 0. Jsou to tedy dvojn´asobky nˇejak´ ych ˇclen˚ u {am }∞ ze tato posloupnost je rostouc´ı, jedn´a se o dvojm=1 . A protoˇ n´asobky jej´ıch n − i nejmenˇs´ıch ˇclen˚ u, tedy o hodnoty 2a1 , . . . , 2an−i . Plat´ı tedy (2.6). Odtud uˇz plyne (2.5). 23

Jeˇstˇe si ukaˇzme, jak vyj´adˇrit optim´aln´ı i v z´avislosti na n. V´ıme, ˇze 3i−1 leˇz´ı v {a1 , . . . , an }, ale 3i ne. Odtud 3i−1 ≤ an < 3i i − 1 ≤ log3 an < i i = blog3 (an )c∗ + 1.

∗

bxc znaˇc´ı doln´ı celou ˇc´ ast x.

24

´ 3. Uloha o hostech N´asleduj´ıc´ı u ´lohu o hostech, zn´amou jakoˇzto m´enage problem, zformuloval roku ´ 1891 francouzsk´ y matematik Edouard Lucas. ´ Uloha 20. Na firemn´ı veˇc´ırek pˇriˇslo n manˇzelsk´ych p´ar˚ u (n ≥ 3). Urˇcete, kolika zp˚ usoby se mohou posadit ke kulat´emu stolu s 2n ˇzidlemi tak, aby se muˇzi a ˇzeny stˇr´ıdali a ˇz´adn´a dvojice nesedˇela vedle sebe. (Dvˇe rozesazen´ı, kde jedno vznikne z druh´eho otoˇcen´ım, povaˇzujeme za r˚ uzn´a.)

3.1

Pˇ r´ımoˇ car´ eˇ reˇ sen´ı

Oznaˇcme Mn poˇcet vˇsech vyhovuj´ıc´ıch rozesazen´ı host˚ u. V [5] je tato u ´loha ˇreˇsena n´asledovnˇe. Nejdˇr´ıv se posad´ı ˇzeny, to je moˇzn´e 2 · n! zp˚ usoby (zvol´ı si lich´e nebo sud´e ˇzidle a nˇe pak usednou libovolnˇe). Dost´av´ame Mn = 2 · n! · mn ,

(3.1)

kde mn je poˇcet vˇsech vyhovuj´ıc´ıch rozesazen´ı muˇz˚ u pro dan´e rozesazen´ı ˇzen. K urˇcen´ı mn lze vyuˇz´ıt princip inkluze a exkluze. ∗ Oznaˇcme Ai mnoˇzinu vˇsech rozm´ıstˇen´ı muˇz˚ u, kde i-t´ y muˇz sed´ı vedle sv´e ˇzeny, i = 1, . . . , n. SnPoˇcet vˇsech moˇzn´ ych rozesazen´ı n muˇz˚ u je n!, pˇriˇcemˇz nevyhovuj´ı pr´avˇe ta z i=1 Ai . Tedy mn = n! − |A1 ∪ . . . ∪ An | = n! −

n X i=1

. . . + (−1)

s

n X

|Ai | +

n X

|Ai ∩ Aj | − . . .

i,j=1 i<j

|Ai1 ∩ . . . ∩ Ais | + . . . + (−1)n |A1 ∩ . . . ∩ An |.

(3.2)

i1 ,...,is =1 i1 <...
V´ yraz

n X

|Ai1 ∩ . . . ∩ Ais | odpov´ıd´a poˇctu vˇsech rozesazen´ı, kdy nˇejak´a

i1 ,...,is =1 i1 <...
s-tice muˇz˚ u sed´ı vedle sv´ ych ˇzen a zbyl´ ych n − s muˇz˚ u sed´ı libovolnˇe, tj. nˇejak´ ym z (n − s)! zp˚ usob˚ u. M˚ uˇzeme ps´at n X

|Ai1 ∩ . . . ∩ Ais | = ds · (n − s)!,

(3.3)

i1 ,...,is =1 i1 <...
kde ds znaˇc´ı poˇcet zp˚ usob˚ u, jimiˇz lze vybrat s-tici muˇz˚ u sed´ıc´ıch vedle sv´ ych ˇzen vˇcetnˇe m´ısta, kde sed´ı (od manˇzelky m˚ uˇzou b´ yt napravo nebo nalevo). Uvˇedom´ıme si, ˇze ds odpov´ıd´a poˇctu zp˚ usob˚ u, jimiˇz lze vybrat s nesousedn´ıch oblouk˚ u z 2n oblouk˚ u na kruˇznici. (Kaˇzd´ y oblouk odpov´ıd´a dvojici sousedn´ıch ˇzidl´ı, na n´ıˇz sed´ı manˇzelsk´ y p´ar.) ∗

Princip inkluze a exkluze je pops´an napˇr. v [5] nebo [16].

25

K v´ ypoˇctu ds vyuˇzijeme znalost toho, jak´ y je poˇcet k-ˇclenn´ ych kombinac´ı nesousedn´ıch prvk˚ u z n prvk˚ u uspoˇra´dan´ ych v ˇradˇe. To zjist´ıme tak, ˇze kaˇzdou takovou kombinaci zak´odujeme posloupnost´ı z k koleˇcek a n−k ˇca´rek, kde koleˇcka odpov´ıdaj´ı vybran´ ym prvk˚ um a ˇca´rky ostatn´ım, viz obr. 3.1.

Obr´azek 3.1: Zp˚ usob zak´odov´an´ı tˇriˇclenn´e kombinace z osmi prvk˚ u, kterou tvoˇr´ı prvky 1, 5 a 7, pomoc´ı koleˇcek a ˇca´rek. ˇ arky rozdˇeluj´ı ˇradu na n − k + 1 pomysln´ C´ ych pˇrihr´adek. V kaˇzd´e pˇrihr´adce je nejv´ yˇse jedno koleˇcko, protoˇze kombinace neobsahuj´ı sousedn´ı prvky. Poˇcet tˇechto kombinac´ı je tedy roven poˇctu zp˚ usob˚ u, jimiˇz lze vybrat k z n − k + 1 pˇrihr´adek, ˇcili   n−k+1 . (3.4) k Nyn´ı vypoˇc´ıt´ame ds . Oblouky na kruˇznici oˇc´ıslujeme 1, 2, . . . 2n. Abychom vyˇreˇsili probl´em, ˇze jsou v kruhu a ne v ˇradˇe, rozdˇel´ıme si situaci na dva pˇr´ıpady podle toho, jestli oblouk 2n je ˇci nen´ı zahrnut do v´ ybˇeru. Pokud nen´ı, vyb´ır´ame s nesousedn´ıch oblouk˚ u z 2n − 1, coˇz lze     (2n − 1) − s + 1 2n − s = s s zp˚ usoby. Pokud je oblouk 2n ve v´ ybˇeru, zb´ yv´a vybrat s − 1 oblouk˚ u z 2n − 3 (oblouky 2, 3, . . . 2n − 2), coˇz lze     (2n − 3) − (s − 1) + 1 2n − s − 1 = s−1 s−1 zp˚ usoby. Celkem tedy         2n − s 2n − s 2n − s − 1 2n − s s = ds = + = + 2n − s s s s−1 s   2n − s 2n = . (3.5) 2n − s s V´ ysledky (3.2), (3.3) a (3.5) dosad´ıme do (3.1) a dost´av´ame, ˇze poˇcet vˇsech vyhovuj´ıc´ıch rozesazen´ı n manˇzelsk´ ych p´ar˚ u okolo stolu je   n X 2n 2n − s s Mn = 2 · n! · (−1) (n − s)! . (3.6) 2n − s s s=0 Pro porovn´an´ı zmiˇ nme jedno podobn´e ˇreˇsen´ı, uveden´e v [2]. Autoˇri zde neupˇrednostˇ nuj´ı ˇzeny ani muˇze, n´ ybrˇz posazuj´ı vˇsechny najednou. Opˇet je vyuˇzit princip inkluze a exkluze, pˇriˇcemˇz je vzato do u ´vahy, ˇze pro kaˇzdou s-tici p´ar˚ u, je poˇcet zp˚ usob˚ u, jak mohou
sedˇet vˇsichni muˇzi vedle sv´ ych ˇzen, stejn´ y, a to Ws . Z n p´ar˚ u jich lze s vybrat ns zp˚ usoby. Dostane se tak   n X s n Mn = (−1) Ws . s s=0 26

Pro s-tici p´ar˚ u lze vybrat ˇzidle ds zp˚ usoby, tyto p´ary pak maj´ı s! moˇznost´ı, kde kter´ y z nich bude sedˇet. D´ale spoleˇcnˇe zvol´ı, kter´a m´ısta pˇr´ısluˇs´ı ˇzen´am a kter´a muˇz˚ um (dvˇe moˇznosti). Skupiny ostatn´ıch muˇz˚ u a ostatn´ıch ˇzen pak mohou kaˇzd´a usednout (n − s)! zp˚ usoby. Celkem tedy Ws = ds · s! · 2 · (n − s)!2 . Za ds se dosad´ı podle (3.5).   2n − s 2n · s! · 2 · (n − s)!2 , Ws = 2n − s s a tedy     n X 2n 2n − s s n Mn = (−1) · s! · 2 · (n − s)!2 = s 2n − s s s=0   n X 2n 2n − s s = 2 · n! · (−1) (n − s)! , 2n − s s s=0 coˇz odpov´ıd´a vztahu (3.6). Vid´ıme, ˇze obˇe zm´ınˇen´a ˇreˇsen´ı vych´az´ı z n´apadu pouˇz´ıt princip inkluze a exkluze a vyˇzaduj´ı v´ ypoˇcet ds . Autoˇri druh´eho ˇreˇsen´ı povaˇzuj´ı za kl´ıˇcovou myˇslenku neposazovat d´amy jako prvn´ı. Jej´ı v´ yznam necht’ posoud´ı ˇcten´aˇr s´am.

3.2

Vˇ eˇ zov´ e polynomy

Nyn´ı si uk´aˇzeme, jak se d´a u ´loha o hostech pˇrehlednˇeji zn´azornit a zp˚ usob jej´ıho ˇ ˇreˇsen´ı zobecnit. Pˇredpokl´adejme, ˇze ˇzeny se jiˇz usadily. Zidle pro muˇze oznaˇcme 1, . . . , n, jak ukazuje obr. 3.2. Na obr. 3.3 jsou pak vybarvena pol´ıˇcka odpov´ıdaj´ıc´ı ˇzidl´ım, kter´e se nach´az´ı vedle ˇzeny dan´eho muˇze. (F znaˇc´ı ˇzeny, M muˇze a manˇzel´e jsou pr´avˇe ti se shodn´ ym indexem.) Vyhovuj´ıc´ımu rozesazen´ı muˇz˚ u zˇrejmˇe odpov´ıd´a takov´ y v´ ybˇer b´ıl´ ych pol´ıˇcek, kdy je z kaˇzd´eho ˇra´dku i kaˇzd´eho sloupce vybr´ano pr´avˇe jedno. 1

F1

1

2

F6

3

4

5

6

M1

F2

6

2

M2 M3

3

M4

F5

F3 5

F4

M5 M6

4

Obr´azek 3.2: Oznaˇcen´ı ˇzidl´ı pro muˇze (n = 6).

Obr´azek 3.3: Zp˚ usob zn´azornˇen´ı omezen´ı pro muˇze (n = 6).

Vyhovuj´ıc´ı rozesazen´ı si m˚ uˇzeme pˇredstavit i jako rozm´ıstˇen´ı n vˇeˇz´ı na b´ıl´a pole, pˇri kter´em na sebe ˇz´adn´e dvˇe nem´ıˇr´ı, vz´ajemnˇe se neohroˇzuj´ı. (Vˇeˇz je ˇsachov´a 27

1

2

3

4

5

6

M2

M1

F1

M5

F6

M2 M3

F2

M4

M1

M4 F5

M5

F3 M3

M6

F4

M6

Obr´azek 3.4: Neohroˇzuj´ıc´ı se vˇeˇze zn´azorˇ nuj´ıc´ı vyhovuj´ıc´ı rozm´ıstˇen´ı muˇz˚ u. figura, kter´a se pohybuje rovnˇe, po sloupci nebo ˇradˇe, o libovoln´ y poˇcet pol´ı.) Jedno takov´e rozm´ıstˇen´ı je uk´az´ano na obr. 3.4. ´ Ulohu o hostech jsme vlastnˇe pˇrevedli na probl´em rozm´ıst’ov´an´ı vˇeˇz´ı. Ten vyˇreˇs´ıme opˇet pomoc´ı principu inkluze a exkluze, dojdeme vˇsak k poznatk˚ um uˇziteˇcn´ ym i k ˇreˇsen´ı jin´ ych u ´loh. Vych´az´ıme ze [3] a [4]. Oznaˇcme Ai mnoˇzinu vˇsech takov´ ych rozestaven´ı n neohroˇzuj´ıc´ıch se vˇeˇz´ı, kde se na i-t´em ˇr´adku nach´az´ı vˇeˇz na ˇcern´em poli. Naˇs´ım c´ılem je tedy urˇcit mn = n! − |A1 ∪ . . . ∪ An |, kde n! je pr´avˇe poˇcet vˇsech moˇzn´ ych rozm´ıstˇen´ı vˇeˇz´ı. Necht’ d´ale vk znaˇc´ı poˇcet vˇsech moˇzn´ ych rozm´ıstˇen´ı k neohroˇzuj´ıc´ıch se vˇeˇz´ı na ˇcern´a pole. Z principu inkluze a exkluze (obdobnˇe jako jsme dostali (3.2) a (3.3)) dost´av´ame n X (−1)k+1 vk (n − k)! mn = n! − k=1

A poloˇz´ıme-li v0 = 1, pak mn =

n X

(−1)k vk (n − k)!

(3.7)

k=0

Zde se na chv´ıli zastavme a uvˇedomme si, ˇze vztah (3.7) je o nˇeco uni” verz´alnˇejˇs´ı“, neˇz bychom se v prvn´ı chv´ıli mohli domn´ıvat. Pˇri jeho odvozen´ı jsme totiˇz nepotˇrebovali zn´at, kter´a pol´ıˇcka jsou vybarvena ˇcernˇe a kter´a b´ıle. Trochu odboˇcme a zaved’me si nˇekolik nov´ ych pojm˚ u. Mnoˇzinu vybarven´ ych pol´ıˇcek ve ˇctverci n kr´at n nazvˇeme s´ıt’. (Jedn´a se tedy o mnoˇzinu uspoˇr´adan´ ych dvojic z ˇc´ısel 1, . . . , n.) Necht’ d´ale vk (S) je poˇcet vˇsech rozm´ıstˇen´ı k neohroˇzuj´ıc´ıch se vˇeˇz´ı v s´ıti S a v0 (S) = 1. Pak X v(x, S) = vx (S)xk k≥0

naz´ yv´ame vˇeˇzov´ ym polynomem s´ıtˇe S. D´ale m˚ uˇzeme hovoˇrit o permutac´ıch s omezuj´ıc´ımi podm´ınkami. Pr´avˇe k urˇcov´an´ı jejich poˇctu n´am vˇeˇzov´e polynomy slouˇz´ı. Necht’ jsou d´any mnoˇziny omezen´ı O1 , . . . , On ⊆ {1, . . . , n}. Permutac´ı s omezuj´ıc´ımi podm´ınkami n prvk˚ u naz´ yv´ame kaˇzdou n-prvkovou permutaci p takovou, ˇze p(i) ∈ / Oi . Oznaˇc´ıme-li pn poˇcet vˇsech 28

permutac´ı s omezuj´ıc´ımi podm´ınkami, dost´av´ame vztah odpov´ıdaj´ıc´ı (3.7), a to pn =

n X

(−1)k vk (S)(n − k)!,

(3.8)

k=0

kde S = {[i, j], j ∈ Oi }. Vˇse si uk´aˇzeme na pˇr´ıkladˇe. ´ Uloha 21. Bˇehem veˇc´ırku se pˇet host˚ u rozhodlo poˇr´ıdit spoleˇcn´e foto. Kolika zp˚ usoby se mohou postavit do ˇrady, jestliˇze prvn´ı z nich nechce st´at pˇresnˇe uprostˇred, tˇret´ı nechce b´yt na kraji, p´at´y naopak na kraji b´yt chce a druh´y se ˇctvrt´ym si ˇz´adn´e podm´ınky nekladou?

Obr´azek 3.5: Omezen´ı pro uspoˇra´d´an´ı host˚ u pˇri focen´ı.

Obr´azek 3.6: Rozklad na dvˇe nez´avisl´e s´ıtˇe.

Situaci zn´azorˇ nuje obr. 3.5. Urˇc´ıme vˇeˇzov´ y polynom pro tuto s´ıt’. Zˇrejmˇe nep˚ ujde rozm´ıstit v´ıc neˇz tˇri vˇeˇze. Pro jednu vˇeˇz existuje ˇsest moˇznost´ı, pro dvˇe vˇeˇze deset a pro tˇri ˇctyˇri, ˇcili v0 (S) = 1, v1 (S) = 6, v2 (S) = 10 a v3 (S) = 4. Vˇeˇzov´ y polynom s´ıtˇe je v(x, S) = 1 + 6x + 10x2 + 4x3 . A poˇcet moˇzn´ ych postaven´ı dan´ ych host˚ u do ˇrady, z´ıskan´ y dosazen´ım do (3.8), je pn = 5! − 6 · 4! + 10 · 3! − 4 · 2! = 28. Zat´ım jsme si ozˇrejmili smysl koeficient˚ u vk (S), nikoli vˇsak samotn´eho polynomu v(x, S). Jde o to, ˇze koeficienty vk (S) se pro sloˇzitˇejˇs´ı s´ıtˇe urˇcuj´ı pˇr´ımo dost obt´ıˇznˇe. Daj´ı se ale vyˇc´ıst“ pr´avˇe z v(x, S). Uk´aˇzeme si dva vztahy, kter´e ” usnadˇ nuj´ı urˇcov´an´ı vˇeˇzov´ ych polynom˚ u. Jejich odvozen´ı je moˇzn´e naj´ıt v [4]. S´ıtˇe S1 a S2 naz´ yv´ame nez´avisl´e, jestliˇze nemaj´ı ˇza´dn´ y spoleˇcn´ y ˇr´adek ani ’ sloupec (tj. pokud [i, j] ∈ S1 a [k, l] ∈ S2 , pak i 6= k a j 6= l). Necht S = S1 ∪ S2 , kde S1 a S2 jsou nez´avisl´e, potom v(x, S) = v(x, S1 ) · v(x, S2 ).

(3.9)

Necht’ S je s´ıt’ a w ∈ S nˇejak´e jej´ı pol´ıˇcko. S´ıt’, kter´a vznikne z S vynech´an´ım pol´ıˇcka w, oznaˇc´ıme Sw a s´ıt’, kter´a vznikne z S vynech´an´ım vˇsech pol´ıˇcek z ˇr´adku a sloupce, v nichˇz se nach´az´ı w, oznaˇc´ıme Sw0 . Plat´ı v(x, S) = v(x, Sw ) + x · v(x, Sw0 ). 29

(3.10)

Uk´aˇzeme si, jak vyuˇz´ıt vztah (3.9) v naˇs´ı u ´loze. S´ıt’ S m˚ uˇzeme rozloˇzit na dvˇe nez´avisl´e s´ıtˇe, viz obr. 3.6. Necht’ S1 je tmavˇs´ı s´ıt’ a S2 svˇetlejˇs´ı. Zˇrejmˇe v1 (S1 ) = 2, v1 (S2 ) = 4 a v2 (S2 ) = 2. Odtud v(x, S1 ) = 1 + 2x v(x, S2 ) = 1 + 4x + 2x2 v(x, S) = v(x, S1 ) · v(x, S2 ) = (1 + 2x)(1 + 4x + 2x2 ) = 1 + 6x + 10x2 + 4x3 .

w

S2

S2w

S2¢ w

Obr´azek 3.7: S´ıtˇe pˇr´ısluˇsej´ıc´ı zvolen´emu pol´ıˇcku w. Aˇckoliv zde je situace jednoduch´a, m˚ uˇzeme si na s´ıti S2 pˇredv´est vztah (3.10). Zvolme w tak, jak je uk´az´ano na obr. 3.7. Dost´av´ame v(x, S2w ) = 1 + 3x v(x, S20 w ) = 1 + 2x v(x, S2 ) = v(x, S2w ) + x · v(x, S20 w ) = (1 + 3x) + x(1 + 2x) = 1 + 4x + 2x2 . Nyn´ı zm´ın´ıme jednu klasickou u ´lohu, a to urˇcen´ı poˇctu permutac´ı bez pevn´ ych ˇ sena je napˇr. v [3] nebo [16]. bod˚ u.∗ Reˇ ´ Uloha 22. Host´e se zvedli od stolu a ˇsli si zatanˇcit, pˇriˇcemˇz se sp´arovali zcela n´ahodnˇe (ale vˇzdy muˇz se ˇzenou). Jak´a je pravdˇepodobnost, ˇze ˇz´adn´y manˇzelsk´y p´ar netanˇc´ı spolu? Vˇsech moˇzn´ ych sp´arov´an´ı je n! a ta, kde ˇza´dn´ı manˇzel´e netanˇc´ı spolu, odpov´ıdaj´ı permutac´ım s omezuj´ıc´ımi podm´ınkami zn´azornˇen´ ym na obr. 3.8.

Obr´azek 3.8: S´ıt’ pro permutace bez pevn´ ych bod˚ u. ∗

Permutace bez pevn´eho bodu je takov´a permutace p, kde pro vˇsechna i plat´ı p(i) 6= i.

30

Vid´ıme, ˇze se jedn´a o s´ıt’, kter´a vnikne sjednocen´ım n nez´avisl´ ych (jednopol´ıˇckov´ ych) s´ıt´ı. Vˇeˇzov´ y polynom kaˇzd´e z nich je 1 + x. Z (3.9) plyne     n 2 n 3 n v(x, S) = (1 + x) = 1 + nx + x + x + . . . + xn 2 3   n n X X n! k n pn = (n − k)! = (−1) (−1)k . k! k k=0 k=0 n

X (−1)k pn = . Abychom z´ıskali lepˇs´ı n! k! k=0 pˇredstavu o tom, k jak´e hodnotˇe se tato pravdˇepodobnost pˇribliˇzuje, pozname∞ X 1 . (−1)k = = 0,368. nejme, ˇze k! e k=0 Nyn´ı se vrat’me k u ´loze o hostech. Urˇc´ıme vˇeˇzov´ y polynom s´ıtˇe z obr. 3.3 (pro libovoln´e n ≥ 3). Oznaˇcme jako w pol´ıˇcko v lev´em doln´ım rohu a hledejme vˇeˇzov´ y 0 polynom pro Sw a Sw (viz obr. 3.9). V´ ysledn´a pravdˇepodobnost je tedy

w S

Sw¢

Sw

´ Obr´azek 3.9: Uloha o hostech – v´ ypoˇcet vˇeˇzov´eho polynomu. yvat m-schodiˇstˇe. S´ıtˇe typu Sw nebo Sw0 sest´avaj´ıc´ı z m pol´ıˇcek budeme naz´ 0 (Tj. Sw je (2n − 1)-schodiˇstˇe a Sw je (2n − 3)-schodiˇstˇe.) Odvod´ıme si vzorec pro vˇeˇzov´ y polynom m-schodiˇstˇe. Chceme-li na schodiˇstˇe um´ıstit k neohroˇzuj´ıc´ıch se vˇeˇz´ı, nesm´ı b´ yt ˇza´dn´e dvˇe z nich na sousedn´ıch pol´ıch. Snadno domysl´ıme, ˇze poˇcet vˇsech moˇzn´ ych rozm´ıstˇen´ı odpov´ıd´a poˇctu k-ˇclenn´ ych kombinac´ı nesousedn´ıch prvk˚ u z m prvk˚ u, tedy   m−k+1 , k jak jsme odvodili dˇr´ıve (viz (3.4)). Na m-schodiˇstˇe m˚ uˇzeme um´ıstit nanejv´ yˇse b(m + 1)/2c vˇeˇz´ı. Pˇr´ısluˇsn´ y polynom je tedy b m+1 c 2

X k=0

 m−k+1 k x . k

(3.11)

Abychom pˇri n´asleduj´ıc´ıch v´ ypoˇctech pˇr
edeˇsli nejasnostem, dohodnˇeme se, ˇze pokud r ˇci s je z´aporn´e nebo s > r, pak rs = 0. Z (3.10) a (3.11) dost´av´ame v(x, S) = v(x, Sw ) + x ·

v(x, Sw0 )

=

 n  X 2n − k k=0

31

k

k

x +x

 n−1  X 2n − k − 2 k=0

k

xk =

 n  X 2n − k

   n  n X 2n − k k 2n − k − 1 k X 2n x . = x + x = 2n − k k k k − 1 k=0 k=0 k=0   n X 2n 2n − k Odtud uˇz mn = (n − k)!. (−1)k 2n − k k k=0 Poznamenejme, ˇze jsme dostali vk (S) = dk , viz (3.5), jak se dalo oˇcek´avat. Smyslem bylo ilustrovat zp˚ usob pouˇzit´ı vˇeˇzov´ ych polynom˚ u, nebot’ jej budeme potˇrebovat k ˇreˇsen´ı dalˇs´ı u ´lohy.

3.3

k

Kdyˇ z uˇ z sed´ı ˇ reditel

Nyn´ı se pod´ıv´ame na variantu u ´lohy o hostech, kdy se k ˇzen´am uˇz jeden muˇz usadil. Budeme se pt´at, kolika zp˚ usoby se mohou rozesadit ostatn´ı muˇzi, a pozdˇeji nav´ıc objasn´ıme, zda poˇcet tˇechto rozesazen´ı z´avis´ı ˇci nez´avis´ı na tom, kter´e m´ısto ˇ sen´ı n´asleduj´ıc´ı u zvolil prvn´ı muˇz. Reˇ ´lohy poch´az´ı z [26]. ´ Uloha 23. Prozrad’me si, ˇze myˇslenka nesedˇet vedle sv´ych manˇzelek vznikla v hlavˇe ˇreditele firmy, na jej´ımˇz veˇc´ırku se pr´avˇe nach´az´ıme. Jeho d˚ uvody ponechme stranou. Ostatn´ım muˇz˚ um toto navrhl ve chv´ıli, kdy uˇz ˇzeny sedˇely. A pak s´am jako prvn´ı zaujal m´ısto. Kolika zp˚ usoby se mohou posadit ostatn´ı muˇzi tak, aby ˇreditelovu poˇzadavku vyhovˇeli? Bez u ´jmy na obecnosti pˇredpokl´adejme, ˇze ˇreditel je muˇz prvn´ı ˇzeny. Necht’ se usadil na r-tou ˇzidli (r ∈ {3, . . . , n}). Budeme urˇcovat vˇeˇzov´ y polynom s´ıtˇe S, kter´a vznikne, vypust´ıme-li ze s´ıtˇe pro u ´lohu o hostech prvn´ı ˇra´dek a r-t´ y 0 sloupec. Poloˇzme A = Sw a B = Sw . Vid´ıme, ˇze s´ıtˇe A i B se kaˇzd´a skl´adaj´ı ze dvou nez´avisl´ ych s´ıt´ı (viz obr. 3.10). S´ıtˇe A1 a B1 jsou (2r − 5)-schodiˇstˇe, A2 je (2(n − r) − 1)-schodiˇstˇe a B2 je 2(n − r)-schodiˇstˇe. Z (3.9), (3.10) a (3.11) dost´av´ame  r−2  X 2r − i − 4 i v(x, A1 ) = v(x, B1 ) = x i i=0  n−r n−r+1 X 2(n − r) − i X 2(n − r) − j + 1 i v(x, A2 ) = x = xj−1 i j−1 i=0 j=0  n−r  n−r+1 X X 2(n − r) − j + 1 2(n − r) − j + 1 j x = xj v(x, B2 ) = j j j=0 j=0 v(x, S) = x · v(x, A1 ) · v(x, A2 ) + v(x, B1 ) · v(x, B2 ) =  n−r+1   r−2  X 2r − i − 4 i X 2(n − r) − j + 2 j = x x = i j i=0 j=0  r−2 n−1 X X 2r − i − 42(n − r) − k + i + 2 = xk . i k−i i=0 k=0 Poˇcet moˇzn´ ych rozesazen´ı zbyl´ ych n − 1 muˇz˚ u pot´e, co se ˇreditel posad´ı na r-tou ˇzidli, je   n−1 r−2  X X 2r − i − 4 2(n − r) − k + i + 2 k (−1) (n − k − 1)! . i k − i i=0 k=0 32

r-1

n-r

w S

A1

B1

A2

B2

A = Sw¢

B = Sw

Obr´azek 3.10: Varianta u ´lohy o hostech, kdy jiˇz sed´ı ˇreditel (n = 10, r = 5). V souvislosti s touto u ´lohou si poloˇzme jeˇstˇe n´asleduj´ıc´ı ot´azku. ´ Uloha 24. Pro kter´a n je poˇcet moˇzn´ych rozesazen´ı ostatn´ıch muˇz˚ u nez´avisl´y na tom, kam usedl ˇreditel? Tj. hled´ame takov´a n, kde je pro vˇsechna r = 3, . . . , n poˇcet moˇzn´ ych roze´ sazen´ı ostatn´ıch muˇz˚ u stejn´ y. Uloha poch´az´ı z [26]. Autor vyslovuje domnˇenku, ˇze ˇreˇsen´ım je pouze mnoˇzina hodnot {3, 4, 6}, ale nem´a pro ni d˚ ukaz. Zde ji dok´aˇzeme. Pˇr´ıpady pro n = 3, . . . , 6 nen´ı probl´em rozebrat kaˇzd´ y zvl´aˇst’ a domnˇenka jim odpov´ıd´a. Zab´ yvejme se tˇemi ostatn´ımi. Budeme tvrdit, ˇze pro n ≥ 7 maj´ı zb´ yvaj´ıc´ı muˇzi v´ıce moˇzn´ ych zp˚ usob˚ u rozesazen´ı, kdyˇz si ˇreditel sedne na ˇctvrtou ˇzidli, neˇz kdyˇz si sedne na tˇret´ı. S´ıtˇe pro obˇe situace zn´azorˇ nuje obr. 3.11. Vznikly ze s´ıtˇe n kr´at n u ´lohy pro hosty vynech´an´ım prvn´ıho ˇra´dku a tˇret´ıho (situace A), resp. ˇctvrt´eho (situace B) sloupce. K d˚ ukazu nebudeme pouˇz´ıvat princip inkluze a exkluze, n´ ybrˇz jenom porovn´avat poˇcty dobr´ ych rozesazen´ı pro dan´e pˇr´ıpady. Takˇze vˇeˇze rozm´ıst’ujeme na b´ıl´a pole. Vid´ıme, ˇze vyjma tˇr´ı horn´ıch ˇr´adk˚ u jsou s´ıtˇe naprosto shodn´e. M˚ uˇzeme si pˇredstavit, ˇze nejdˇr´ıv rozm´ıst´ıme n − 4 vˇeˇz´ı na n − 4 spodn´ıch ˇr´adk˚ u (tj. do prostoru pod ˇcarou). Pro kaˇzd´e rozm´ıstˇen´ı n−4 doln´ıch“ vˇeˇz´ı pak m˚ uˇzeme porov” n´avat poˇcty moˇzn´ ych rozm´ıstˇen´ı zb´ yvaj´ıc´ıch tˇr´ı horn´ıch“ vˇeˇz´ı ve tˇrech vrchn´ıch ” ˇra´dc´ıch pro situace A a B. 33

A

B

Obr´azek 3.11: S´ıtˇe pro situace, kdy ˇreditel sed´ı na tˇret´ı (A) a na ˇctvrt´e (B) ˇzidli. Rozebereme jednotliv´e pˇr´ıpady podle toho, kter´e sloupce z˚ ustanou voln´e po rozm´ıstˇen´ı doln´ıch“ vˇeˇz´ı: ” • Je-li obsazen tˇret´ı sloupec zleva, maj´ı horn´ı“ vˇeˇze v A i B stejn´e moˇznosti, ” poˇcet z´ıskan´ ych rozestaven´ı je tedy v obou situac´ıch stejn´ y. • Je-li voln´ y tˇret´ı sloupec zleva a oba sloupce s n´ım soused´ıc´ı, maj´ı v A i B horn´ı“ vˇeˇze pr´avˇe jeden zp˚ usob, jak se rozm´ıstit. ” • Je-li voln´ y tˇret´ı sloupec zleva a oba sloupce s n´ım soused´ıc´ı jsou obsazeny, je v A i B pr´avˇe pro jednu horn´ı“ vˇeˇz d´ano, kam se um´ıst´ı (jen jedna z nich ” m˚ uˇze b´ yt ve tˇret´ım sloupci zleva), zb´ yvaj´ıc´ı dvˇe maj´ı dvˇe moˇznosti jak se rozm´ıstit. • Je-li voln´ y druh´ y a tˇret´ı sloupec zleva a ˇctvrt´ y je obsazen, jsou v situaci A dvˇe moˇznosti rozm´ıstˇen´ı horn´ıch“ vˇeˇz´ı, ale v situaci B pouze jedna. ” • Naopak, je-li voln´ y tˇret´ı a ˇctvrt´ y sloupec zleva a druh´ y je obsazen, je v situaci A jedin´a moˇznost rozm´ıstˇen´ı horn´ıch“ vˇeˇz´ı a v situaci B dvˇe. ” Vid´ıme, ˇze pro porovn´an´ı jsou podstatn´e jenom posledn´ı dva body. Necht’ x je poˇcet rozm´ıstˇen´ı doln´ıch“ vˇeˇz´ı odpov´ıdaj´ıc´ıch pˇredposledn´ımu bodu a y posledn´ı” mu. Rozd´ıl poˇct˚ u moˇzn´ ych rozesazen´ı v A a B je zˇrejmˇe (2x+y)−(x+2y) = x−y. Chceme-li uk´azat, ˇze v situaci B je poˇcet vˇsech moˇzn´ ych rozesazen´ı vˇetˇs´ı neˇz v situaci A, staˇc´ı dok´azat, ˇze y > x. To jde snadno. Uvˇedom´ıme si, ˇze co se t´ yˇce doln´ıch“ vˇeˇz´ı, nem˚ uˇze ve ˇctvrt´em sloupci zleva st´at vˇeˇz ve ˇctvrt´em ˇr´adku shora, ” zat´ımco na druh´ y sloupec ˇz´adn´a omezen´ı nejsou. Odtud vid´ıme, ˇze y je vˇetˇs´ı neˇz x pr´avˇe o poˇcet rozm´ıstˇen´ı doln´ıch“ vˇeˇz´ı, pˇri nichˇz stoj´ı vˇeˇz ve druh´em sloupci ” na ˇctvrt´em ˇra´dku (a tˇret´ı a ˇctvrt´ y sloupec je voln´ y). Kaˇzd´ y uˇz s´am domysl´ı, ˇze pro n ≥ 7 aspoˇ n jedno takov´e rozm´ıstˇen´ı existuje. T´ım je domnˇenka dok´az´ana. Jeˇstˇe si povˇezme, proˇc argument z tohoto d˚ ukazu nefunguje pro n = 6. Vid´ıme (viz obr. 3.12), ˇze zde je jeˇstˇe pˇr´ıliˇs st´ısnˇen´ y“ prostor. Um´ıst´ıme-li vˇeˇz ve ˇctvrt´em ” ˇra´dku na druh´ y sloupec, nem˚ uˇzeme um´ıstit vˇeˇz na spodn´ı ˇra´dek tak, aby z˚ ustal tˇret´ı a ˇctvrt´ y sloupec voln´ y.

34

Obr´azek 3.12: Situace pro n = 6.

3.4

Nˇ ekolik pozn´ amek

Vrat’me se nyn´ı zp´atky k u ´loze o hostech. Jeˇstˇe je totiˇz vhodn´e zm´ınit, ˇze pro ni ˇ sen´ı z roku existuj´ı i rekurentn´ı ˇreˇsen´ı, historicky starˇs´ı neˇz ta v´ yˇse zm´ınˇen´a. Reˇ 1903 od H. M. Taylora je pops´ano v [8]. Tak´e na poˇc´atku pˇredpokl´ad´a, ˇze ˇzeny se jiˇz posadily. Je pomˇernˇe sloˇzit´e a vede na soustavu rekurentn´ıch rovnic An+1 = (n − 2)An + (3n − 4)Bn + Cn Bn+1 = An + Bn Cn+1 = (2n − 1)Bn + Cn , kde An je poˇcet vˇsech vyhovuj´ıc´ıch rozesazen´ı n muˇz˚ u (tj. ˇz´adn´ y muˇz nesed´ı vedle sv´e ˇzeny). Bn je poˇcet vˇsech moˇzn´ ych rozesazen´ı n − 1 zb´ yvaj´ıc´ıch muˇz˚ u tak, aby ˇza´dn´ y z nich nesedˇel vedle sv´e ˇzeny, jestliˇze jeden muˇz jiˇz sed´ı, a to vedle sv´e ˇzeny. A Cn je poˇcet vˇsech moˇzn´ ych rozesazen´ı n − 1 zb´ yvaj´ıc´ıch muˇz˚ u tak, aby pr´avˇe jeden z nich sedˇel vedle sv´e ˇzeny, jestliˇze jeden muˇz jiˇz sed´ı, a to vedle sv´e ˇzeny. Z t´eto soustavy rovnic je d´ale odvozena tzv. Laisantova rekuretn´ı formule (n − 1)An+1 = (n2 − 1)An + (n + 1)An−1 + 4 · (−1)n

pro n ≥ 4.

Pomˇernˇe snadnou u ´pravou ji lze pˇrev´est do podoby, odkud je v´ ypoˇcet An o nˇeco jednoduˇsˇs´ı, a to An = nAn−1 + 2An−2 − (n − 4)An−3 − An−4

pro n ≥ 7,

pˇriˇcemˇz A3 = 1, A4 = 2, A5 = 13 a A6 = 80. Jeˇstˇe pˇripomeˇ nme, ˇze poˇcet vˇsech ˇreˇsen´ı u ´lohy o hostech je Mn = 2n! · An . Pro naˇsi pˇredstavu si z´avˇerem uvedeme nˇekolik prvn´ıch hodnot An a pravdˇepodobnost, s jakou se muˇzi posad´ı tak, aby nebyli vedle sv´ ych ˇzen, rozesad´ı-li se zcela n´ahodnˇe. Ta je zˇrejmˇe pn = An /n!. Vˇse ukazuje tabulka 3.1. Ve [14] je 1 . dok´az´ano, ˇze lim pn = 2 = 0,1353. n→∞ e

35

n An 3 1 4 2 5 13 6 80 7 579 8 4 738 9 43 387 10 439 792 11 4 890 741 12 59 216 642 13 775 596 313 14 10 927 434 464 15 164 806 435 783

pn 0,1667 0,0833 0,1083 0,1111 0,1149 0,1175 0,1196 0,1212 0,1225 0,1236 0,1246 0,1253 0,1260

´ Tabulka 3.1: Uloha o hostech – hodnoty An a pn .

36

4. Hlasovac´ı probl´ em ´ Uloha 25. Ve volb´ach soupeˇr´ı dva kandid´ati. Prvn´ı z nich dostal a hlas˚ u, druh´y b hlas˚ u, pˇriˇcemˇz a ≥ kb, kde k je pˇrirozen´e ˇc´ıslo. Jak´a je pravdˇepodobnost, ˇze v pr˚ ubˇehu cel´eho sˇc´ıt´an´ı mˇel prvn´ı kandid´at v´ıc hlas˚ u, neˇz je k-n´asobek poˇctu dosud seˇcten´ych hlas˚ u jeho soupeˇre? Tento probl´em zveˇrejnil v roce 1887 Joseph Bertrand, jen pro k = 1, a n´aslednˇe ´ Emile Barbier, jiˇz v t´eto obecn´e podobˇe. S ˇreˇsen´ım pro k = 1 brzy pˇriˇsel D´esir´e Andr´e. Prvn´ı ˇreˇsen´ı obecn´eho probl´emu pak roku 1923 zaznamenal A. Aeppli. Nejzaj´ımavˇejˇs´ı je, ˇze existuje pomˇernˇe dost zp˚ usob˚ u, jak se dopracovat k odpovˇedi. Nˇekter´e z nich si uk´aˇzeme n´ıˇze. Poch´az´ı z [21] a [22], kde je moˇzno naj´ıt i mnoho odkaz˚ u t´ ykaj´ıc´ıch se tohoto t´ematu.

4.1

ˇ sen´ı pomoc´ı pˇ Reˇ reklopen´ı

Nejdˇr´ıv si ujasnˇeme, co pˇresnˇe budeme poˇc´ıtat. Pˇredpokl´adejme, ˇze hlasy jsou sˇc´ıt´any v n´ahodn´em poˇrad´ı jeden po druh´em. M˚ uˇzeme tedy ˇr´ıct, ˇze jsou na zaˇc´atku uspoˇr´ad´any do nˇejak´e posloupnosti. N´as zaj´ım´a pomˇer vyhovuj´ıc´ıch posloupnost´ı ku vˇsem. Hlas pro prvn´ıho kandid´ata znaˇcme A a hlas pro druh´eho B. Protoˇze hlasy pro kaˇzd´eho z kandid´at˚ u jsou navz´ajem nerozliˇsiteln´e, je poˇcet vˇsech moˇzn´ ych posloupnost´ı   a+b . (4.1) a Z a+b pozic v uspoˇr´ad´an´ı jich totiˇz a vyb´ır´ame pro hlasy A. Napˇr. pro a = 5, b = 2 a k = 2 existuje 21 posloupnost´ı, ale pouze tˇri z nich vyhovuj´ı (nazvˇeme je dobr´e). Konkr´etnˇe AAAAABB, AAAABAB a AAABAAB. Naopak AAAABBA je nevyhovuj´ıc´ı (ˇspatn´a), protoˇze po ˇsest´em kroku (v situaci AAAABB) nem´a prvn´ı kandid´at v´ıc neˇz dvojn´asobek poˇctu hlas˚ u druh´eho kandid´ata. V´ ysledn´a pravdˇepodobnost je tedy 3/21 = 1/7. Nejdˇr´ıve budeme u ´lohu ˇreˇsit pro k = 1, tj. zkoum´ame, zda m´a prvn´ı kandid´at po celou dobu sˇc´ıt´an´ı v´ıc hlas˚ u neˇz kandid´at druh´ y. Posloupnost hlasovac´ıch l´ıstk˚ u budeme zn´azorˇ novat jako cestu ve ˇctvercov´e s´ıti zaˇc´ınaj´ıc´ı v pr˚ useˇc´ıku os, pˇriˇcemˇz l´ıstku A odpov´ıd´a krok∗ (1, 1) a l´ıstku B krok (1, −1). Kaˇzd´a cesta tak zˇrejmˇe konˇc´ı v bodˇe [a + b, a − b]. Dobr´e cesty jsou ty, kter´e jsou po celou dobu nad osou x. Napˇr. posloupnost AABBABBAAA zn´azorn´ıme jako na obr´azku 4.1. Vid´ıme, ˇze je ˇspatn´a, protoˇze se dot´ yk´a osy x (a dokonce pod ni pozdˇeji i klesne). Prvn´ım ˇspatn´ ym krokem je ten ˇctvrt´ y. Cesty zaˇc´ınaj´ıc´ı hlasem A, resp. B, budeme naz´ yvat A-cesty, resp. B-cesty. A nyn´ı m˚ uˇzeme pˇristoupit k ˇreˇsen´ı. Nejdˇr´ıv si uvˇedom´ıme, ˇze kaˇzd´a B-cesta je urˇcitˇe ˇspatn´a. B-cest je celkem   a+b−1 , (4.2) a protoˇze ze zbyl´ ych a + b − 1 pozic jich a vyb´ır´ame pro l´ıstky A. Kl´ıˇcovou ot´azkou pro n´as bude, kolik A-cest je tak´e ˇspatn´ ych. Uk´aˇzeme si, ˇze poˇcet ˇspatn´ ych A-cest ∗

Pojmem krok (x, y)“ rozum´ıme posunut´ı o vektor (x, y). ”

37

Obr´azek 4.1: Zn´azornˇen´ı posloupnosti hlas˚ u AABBABBAAA jakoˇzto cesty ve ˇctvercov´e s´ıti. je stejn´ y jako poˇcet vˇsech B-cest, a to tak, ˇze mezi mnoˇzinami tˇechto cest najdeme bijekci.

Obr´azek 4.2: Bijekce mezi B-cestami a ˇspatn´ ymi A-cestami. Pro ˇspatnou A-cestu vezmeme prvn´ı m´ısto jej´ıho dotyku s osou x. Cel´ y poˇc´ateˇcn´ı u ´sek cesty aˇz po tento bod pak podle osy x pˇreklop´ıme. Dostaneme tak ´ e stejn´ B-cestu (viz obr´azek 4.2). Uplnˇ y postup pouˇzijeme k nalezen´ı ˇspatn´e A-cesty pˇr´ısluˇsej´ıc´ı dan´e B-cestˇe. A bijekce je na svˇetˇe. Zjistili jsme tedy, ˇze a+b−1 ˇspatn´ ych A-cest je tak´e . Odeˇcten´ım vˇsech ˇspatn´ ych cest od (4.1) a dost´av´ame       a+b a+b−1 a+b (a + b − 1)! b a + b · · = −2 = −2· a!(b − 1)! b a + b a a a      a−b a+b a+b 2b = . (4.3) = 1− a+b a+b a a Pravdˇepodobnost, ˇze prvn´ı kandid´at mˇel v pr˚ ubˇehu sˇc´ıt´an´ı vˇzdy v´ıce hlas˚ u neˇz a−b druh´ y, je tedy . a+b Pro zaj´ımavost si uk´aˇzeme jeˇstˇe jin´ y zp˚ usob, jak zjistit poˇcet ˇspatn´ ych A-cest. Budeme hledat bijekci mezi ˇspatn´ ymi A-cestami a posloupnostmi tvoˇren´ ymi a hlasy A a b − 1 hlasy B. Mˇejme ˇspatnou posloupnost zaˇc´ınaj´ıc´ı hlasem pro A a najdˇeme prvn´ı B, kter´e ji kaz´ı. To rozdˇeluje posloupnost na dva u ´seky. B odstraˇ nme au ´seky prohod’me. Novˇe vznikl´a posloupnost je tvoˇrena a hlasy A a b − 1 hlasy B. Pˇrehlednˇe je vˇse zn´azornˇeno na obr. 4.3. Jak pro posloupnost tvoˇrenou a hlasy A a b − 1 hlasy B naj´ıt j´ı odpov´ıdaj´ıc´ı ˇspatnou posloupnost zaˇc´ınaj´ıc´ı hlasem A? Postupujeme odzadu aˇz k prvn´ımu A, po jehoˇz zapoˇcten´ı poˇcet A pˇrev´ yˇs´ı o jedna poˇcet B. Vlevo od tohoto A posloupnost rozdˇel´ıme na dvˇe ˇca´sti, ty prohod´ıme a vloˇz´ıme mezi nˇe B (viz obr. 4.4). Odtud uˇz plyne, ˇze poˇcet ˇspatn´ ych A-cest odpov´ıd´a hodnotˇe (4.2).

38

A A B B A B A A

odebrat

A A B

A B A A

A B A A A A B

prohodit

Obr´azek 4.3: Pro ˇspatnou A-cestu hled´ame cestu tvoˇrenou a hlasy A a b − 1 hlasy B, (a = 5, b = 3). A B A A A A B

vyhledat

A B A A

A A B

prohodit

A A B B A B A A

dodat

Obr´azek 4.4: Pro cestu tvoˇrenou a hlasy A a b − 1 hlasy B hled´ame ˇspatnou A-cestu, (a = 5, b = 3).

4.2

ˇ sen´ı pomoc´ı otoˇ Reˇ cen´ı

Nyn´ı se pod´ıvejme, jak se u ´loha zmˇen´ı pro k > 1. Posloupnost hlas˚ u m˚ uˇzeme opˇet zn´azorˇ novat jako cestu ve ˇctvercov´e s´ıti. Podstatn´e je to, ˇze B bude nyn´ı odpov´ıdat kroku (1, −k), nebot’ jeden hlas B vyvaˇzuje pro naˇse potˇreby k hlas˚ u A (dobr´e cesty jsou opˇet ty, kter´e se po celou dobu drˇz´ı nad osou x). T´ım, ˇze kroky pro A a B nyn´ı nejsou symetrick´e a po pˇreklopen´ı ˇc´asti cesty podle osy x by novˇe vznikl´e kroky neodpov´ıdaly ani A, ani B, nelze uplatnit stejn´ y zp˚ usob jako v pˇredeˇsl´e sekci. Porad´ıme si ale podobnˇe. Budeme poˇc´ıtat, kolik je ˇspatn´ ych cest, pˇriˇcemˇz si je rozdˇel´ıme podle toho, kde konˇc´ı jejich prvn´ı ˇspatn´ y krok. To m˚ uˇze b´ yt na ose x nebo aˇz k jednotek pod n´ı. Oznaˇcme Bi mnoˇzinu tˇech cest, jejichˇz prvn´ı ˇspatn´ y krok konˇc´ı i jednotek pod osou x, i = 0, . . . , k. Mnoˇziny Bi jsou zˇrejmˇe po dvou disjunktn´ı. Nav´ıc do Bk patˇr´ı pr´avˇe ty cesty, kter´e zaˇc´ınaj´ı krokem dol˚ u. Jejich poˇcet jiˇz zn´ame, viz (4.2). Kl´ıˇcov´ ym pro naˇse ˇreˇsen´ı je fakt, ˇze |Bi | = |Bk | pro vˇsechna i = 0, . . . , k − 1. To si uk´aˇzeme pomoc´ı bijekce mezi mnoˇzinami Bi a Bk . Pro cestu z Bi najdeme pˇr´ısluˇsnou cestu z Bk t´ım, ˇze poˇc´ateˇcn´ı u ´sek cesty vˇcetnˇe prvn´ıho ˇspatn´eho kroku, ◦ otoˇc´ıme o 180 tak, aby se koncov´e vrcholy tohoto u ´seku zobrazily jeden na druh´ y (viz obr´azek 4.5). Urˇcitˇe dostaneme cestu z Bk , protoˇze ot´aˇcen´ yu ´sek konˇc´ı krokem (1, −k), kter´ yˇzto bude po otoˇcen´ı prvn´ım krokem dol˚ u. Obdobn´ ym zp˚ usobem dostaneme pro cestu z Bk zp´atky cestu z Bi , a to tak, ˇze ot´aˇc´ıme u ´sek cesty konˇc´ıc´ı v prvn´ım vrcholu leˇz´ıc´ım i jednotek pod osou x. (Takov´ y vrchol urˇcitˇe existuje, nebot’ stoup´ame“ pouze po jedn´e a vzhledem k pˇredpokladu a ≥ kb se ” cesta zaˇc´ınaj´ıc´ı od B mus´ı nˇekde dotknout osy x.) Zjistili jsme tedy   a+b−1 |Bi | = pro i = 0, . . . , k. a Odtud po odeˇcten´ı od (4.1) dost´av´ame, ˇze poˇcet vˇsech vyhovuj´ıc´ıch uspoˇr´ad´an´ı hlas˚ u je          a+b a − kb a + b a+b a+b−1 (k + 1)b = . − (k + 1) = 1− a+b a a+b a a a Pravdˇepodobnost, ˇze prvn´ı kandid´at mˇel po celou dobu sˇc´ıt´an´ı v´ıc neˇz k-n´asobek a − kb poˇctu hlas˚ u druh´eho, je tedy . a+b 39

Obr´azek 4.5: Bijekce mezi B1 a Bk (k = 3, a = 8, b = 2).

4.3

ˇ sen´ı pomoc´ı matematick´ Reˇ e indukce

ˇ sen´ı u Reˇ ´lohy 25 jiˇz zn´ame. Oznaˇc´ıme-li Nk (a, b) poˇcet vˇsech vhodn´ ych uspoˇra´d´an´ı hlas˚ u pro dan´a a, b, k, m˚ uˇzeme ps´at   a − kb a + b Nk (a, b) = . (4.4) a+b a Pokud vztah (4.4) uhodneme“, nen´ı jiˇz probl´em dok´azat jej indukc´ı vzhledem ” k a, b, a to n´asledovnˇe. V prvn´ım kroku ovˇeˇr´ıme, ˇze vztah splˇ nuje Nk (a, 0) = 1 pro vˇsechna a > 0 (pokud jsou vˇsechny hlasy jen A, pak jdou uspoˇr´adat pr´avˇe jedn´ım zp˚ usobem, a ten je spr´avn´ y) a d´ale Nk (kb, b) = 0 pro vˇsechna b > 0 (pˇr´ısluˇsn´a cesta pro a = kb konˇc´ı na ose x, a tud´ıˇz je vˇzdy ˇspatn´a). Necht’ d´ale a > kb. Ve druh´em kroku pˇredpokl´adejme, ˇze dokazovan´ y vztah plat´ı pro vˇsechny dvojice [p, q], kde 0 ≤ q ≤ b a kq ≤ p ≤ a, vyjma [0, 0], kde nen´ı definov´an, a [a, b]. Dok´aˇzeme, ˇze pak plat´ı i pro [a, b]. K tomu vyuˇzijeme rovnici Nk (a, b) = Nk (a − 1, b) + Nk (a, b − 1). Prav´a strana odpov´ıd´a souˇctu dobr´ ych cest konˇc´ıc´ıch hlasem pro A a dobr´ ych cest konˇc´ıc´ıch hlasem pro B. D´ıky indukˇcn´ımu pˇredpokladu tak dost´av´ame     a − k(b − 1) a + (b − 1) (a − 1) − kb (a − 1) + b + = Nk (a, b) = (a − 1) + b a−1 a + (b − 1) a     a − kb − 1 a a+b a − kb + k b a+b = + = · · a+b−1 a+b a a+b−1 a+b a     (a − kb)(a + b − 1) a + b a − kb a + b = = , (a + b)(a + b − 1) a a+b b ˇcili v´ ysledn´a pravdˇepodobnost je (a − kb)/(a + b).

4.4

ˇ sen´ı uspoˇ Reˇ r´ ad´ an´ım do kruhu

N´asleduj´ıc´ı ˇreˇsen´ı je fascinuj´ıc´ı svoj´ı jednoduchost´ı. Hledanou pravdˇepodobnost zde dostaneme, aniˇz bychom poˇc´ıtali vˇsechny posloupnosti. 40

Uspoˇra´dejme vˇsech a + b hlasovac´ıch l´ıstk˚ u do kruhu (libovoln´ ym zp˚ usobem). Od kter´ehokoliv l´ıstku m˚ uˇzeme zaˇc´ıt a ve zvolen´em smˇeru sˇc´ıtat hlasy. Uk´aˇzeme, ˇze pr´avˇe a − kb l´ıstk˚ u je vhodn´ ym zaˇc´atkem, tj. posloupnost, kterou takto dostaneme, splˇ nuje podm´ınky zad´an´ı. Konkr´etnˇe si m˚ uˇzeme pˇredstavit, ˇze na m´ıstˇe hlasu A je ˇc´ıslo 1 a na m´ıstˇe B je −k. Tato ˇc´ısla postupnˇe sˇc´ıt´ame, pˇriˇcemˇz dobr´a posloupnost je takov´a, pro kterou je pr˚ ubˇeˇzn´ y souˇcet st´ale kladn´ y. Kl´ıˇcov´ ym pozorov´an´ım je to, ˇze vypust´ıme-li z kruhu souvisl´ yu ´sek (4.5) 1, . . . , 1, −k, | {z } k jedniˇ cek

neodstran´ıme ˇza´dn´ y vhodn´ y zaˇca´tek. (Pˇri poˇc´ıt´an´ı od kter´ekoliv z tˇechto jedniˇcek bychom se po odeˇcten´ı k dostali na nulu nebo pod ni.) D´ıky tomu, ˇze souˇcet tohoto u ´seku je 0 a −k je aˇz na jeho konci, neovlivn´ı jeho vynech´an´ı skuteˇcnost, zda ˇc´ısla leˇz´ıc´ı mimo nˇej jsou ˇci nejsou vhodn´ ym poˇc´atkem. ´ Useky (4.5) postupnˇe vypouˇst´ıme tak dlouho, dokud v kruhu zb´ yv´a nˇejak´e −k. Takov´ yu ´sek urˇcitˇe vˇzdy existuje, protoˇze aktu´aln´ı poˇcet hlas˚ u A v kruhu je vˇzdy alespoˇ n k-n´asobkem aktu´aln´ıho poˇctu hlas˚ u B. Abychom se zbavili vˇsech −k, odstran´ıme u ´sek (4.5) celkem b-kr´at. Na z´avˇer tedy zb´ yv´a v kruhu pr´avˇe a − kb jedniˇcek. Protoˇze v nˇem jiˇz nejsou z´aporn´e hodnoty, je zˇrejmˇe kaˇzd´a z nich vhodn´ ym poˇca´tkem. Tj. z a + b posloupnost´ı zn´azornˇen´ ych pomoc´ı jednoho kruhu, jich je a − kb dobr´ ych. Cel´ y postup ukazuje obr´azek 4.6. Pro kaˇzdou posloupnost existuje pr´avˇe jeden kruh, kter´ ym je zn´azornˇena (povaˇzujeme-li pootoˇcen´e kruhy za stejn´e). M˚ uˇze se st´at, ˇze nˇekter´a posloupnost je v dan´em kruhu v´ıcekr´at (pokud je kruh tvoˇren ze dvou nebo v´ıce shodn´ ych u ´sek˚ u), ale pak jsou v kruhu zastoupeny ve stejn´em poˇctu i ostatn´ı posloupnosti, kter´e tento kruh zn´azorˇ nuje. Nic to tedy nemˇen´ı na skuteˇcnosti, ˇze pomˇer dobr´ ych posloupnost´ı ku vˇsem je (a − kb)/(a + b), coˇz jsme chtˇeli dok´azat.

A

1

A

A A

A

A

1

1

-2

A

-2 1

1

1

1 1

B B

1

1

B

1

-2

1 1

-2 1

-2

1

1 1

-2 1 A

1 1 -2 1

-2

1

1 1

-2 1

B

A 1

-2 1

-2

A

A

1 1

1

-2

A

A

B B

A

Obr´azek 4.6: Odeb´ır´an´ı z kruhu pro a = 7, b = 3, k = 2. Z posloupnost´ı zn´azornˇen´ ych t´ımto kruhem je dobr´a pouze ta zaˇc´ınaj´ıc´ı vyznaˇcen´ ym A, ˇcili AAAAABABAB.

41

4.5

ˇ sen´ı pomoc´ı kl´ıˇ Reˇ cov´ ych vrchol˚ u

N´asleduj´ıc´ı d˚ ukaz je o nˇeco komplikovanˇejˇs´ı, coˇz mu vˇsak neub´ır´a na zaj´ımavosti. Oznaˇcme A = A(a, b, k) mnoˇzinu vˇsech cest pro dan´a a, b, k. Necht’ P je libovoln´a cesta z A. Pro P definujeme mnoˇzinu L(P ) obsahuj´ıc´ı a − kb hodnot x-ov´ ych souˇradnic vrchol˚ u P n´asleduj´ıc´ım zp˚ usobem: Z hodnot y-ov´ ych souˇradnic vrchol˚ u P najdˇeme tu nejmenˇs´ı a oznaˇcme ji y0 . Do mnoˇziny L(P ) pak pro kaˇzd´e y = y0 , y0 + 1, . . . , y0 + (a − kb) − 1 zaˇrad´ıme nejvˇetˇs´ı x takov´e, ˇze [x, y] ∈ P (viz obr´azek 4.7). Poznamenejme, ˇze pro vˇsechny P plat´ı L(P ) ⊂ {0, . . . , a + b − 1}.

Obr´azek 4.7: Definice L(P ) – uk´azka pro dvˇe cesty z A(9, 3, 2). V prvn´ım pˇr´ıpadˇe L(P ) = {4, 5, 9}, ve druh´em L(P ) = {0, 4, 11}. D´ale pro i = 0, 1, . . . , a + b − 1 definujeme Mi = {P ∈ A|i ∈ L(P )}. Zˇrejmˇe plat´ı   X a+b |Mi | = (a − kb) , (4.6) a i
a+b protoˇze |A| = a a |L(P )| = a − kb pro vˇsechny P ∈ A. Nejdˇr´ıve si uvˇedom´ıme, ˇze |M0 | odpov´ıd´a poˇctu vˇsech dobr´ ych cest. Mezi M0 a dobr´ ymi cestami totiˇz existuje snadno odhaliteln´a bijekce: • P dobr´a ⇒ [0, 0] nejniˇzˇs´ı vrchol v P ⇒ 0 ∈ L(P ) ⇒ P ∈ M0 . • P ∈ M0 ⇒ ˇza´dn´ y dalˇs´ı vrchol P neleˇz´ı na ose x ⇒ P dobr´a. Stˇeˇzejn´ım pro n´aˇs d˚ ukaz bude ta skuteˇcnost, ˇze |M0 | = |Mi | pro vˇsechna i = 1, 2, . . . , a + b − 1. Protoˇze mnoˇzin Mi je celkem a + b, vzhledem ke (4.6) dostaneme   a − kb a + b , M0 = b a+b coˇz je n´am dobˇre zn´am´ y v´ ysledek. Zb´ yv´a tedy naj´ıt bijekci mezi M0 a Mi . Nejdˇr´ıv uk´aˇzeme P = XY ∗ ∈ Mi (X je prvn´ıch i krok˚ u P ) ⇒ Q = Y X dobr´a. Prvn´ı vrchol u ´seku Y je zˇrejmˇe jeho nejn´ıˇze poloˇzen´ ym. Jinak by nemohlo platit i ∈ L(P ), nebot’ by se nˇekde napravo od [i, yi ] nach´azel ve v´ yˇsce yi jin´ y vrchol. V cestˇe Q se tedy u ´sek Y udrˇz´ı nad osou x a cestu Q nepokaz´ı. M˚ uˇze nˇeco pokazit n´asleduj´ıc´ı u ´sek X? V p˚ uvodn´ı cestˇe P byly y-ov´e souˇradnice prvn´ıho a ∗

Z´ apisem P = XY rozum´ıme, ˇze P je tvoˇrena posloupnost´ı krok˚ u X a za n´ı n´asleduj´ıc´ı posloupnost´ı Y .

42

posledn´ıho vrcholu u ´seku Y rovny yi a a − kb. V nov´e cestˇe Q tedy bude y-ov´a souˇradnice posledn´ıho vrcholu Y rovna a − kb − yi . V jak´e v´ yˇsce se nach´azel nejn´ıˇze poloˇzen´ y vrchol z X v P ? Urˇcitˇe ne n´ıˇze neˇz v yi − (a − kb) + 1, protoˇze yi je mezi a − kb nejniˇzˇs´ımi hodnotami y-ov´ ych souˇradnic (nebot’ i ∈ L(P )). Pˇritom X zaˇc´ınal v [0, 0]. V Q je tedy nejn´ıˇze poloˇzen´ y vrchol X ve v´ yˇsce nejm´enˇe (yi − (a − kb) + 1) + (a − kb − yi ) = 1, ˇcili nad osou x. Takˇze Q je dobr´a, tj. Q ∈ M0 . D´ale uk´aˇzeme Q = Y X ∈ M0 (X je posledn´ıch i krok˚ u Q) ⇒ P = XY ∈ Mi . Dokazujeme, ˇze i ∈ L(P ). Tedy, ˇze napravo od [i, yi ] neexistuje vrchol se stejnou y-ovou souˇradnic´ı a ˇze yi patˇr´ı mezi a − kb nejniˇzˇs´ıch hodnot y-ov´ ych souˇradnic vrchol˚ u v P . Nejdˇr´ıv si uvˇedom´ıme, ˇze u ´sek Y byl v Q po celou dobu nad osou x. V P tedy bude po celou dobu nad u ´rovn´ı yi , coˇz mj. znamen´a, ˇze napravo od [i, yi ] neexistuje ve stejn´e v´ yˇsce (a ani n´ıˇze) ˇz´adn´ y dalˇs´ı vrchol. Dalˇs´ı skuteˇcnost´ı je to, ˇze v Q je posledn´ı vrchol u ´seku X ve v´ yˇsce a − kb a nejniˇzˇs´ı vrchol ve v´ yˇsce nejm´enˇe 1. Odtud plyne, ˇze v P je rozd´ıl y-ov´ ych souˇradnice i-t´eho vrcholu a nejn´ıˇze poloˇzen´eho vrcholu nejv´ yˇse a − kb − 1, hodnota yi tedy patˇr´ı mezi a − kb nejniˇzˇs´ıch a i ∈ L(P ). T´ım je d˚ ukaz hotov.

4.6

Souvislost s Catalanov´ ymi ˇ c´ısly

Z´avˇerem si uk´aˇzeme, jak hlasovac´ı probl´em souvis´ı s Catalanov´ ymi ˇc´ısly. Lehce jej pro tento u ´ˇcel pozmˇen´ıme. ´ Uloha 26. Oba kandid´ati dostali ve volb´ach shodn´y poˇcet hlas˚ u. Kolika zp˚ usoby lze uspoˇr´adat hlasovac´ı l´ıstky tak, aby prvn´ı kandid´at mˇel po celou dobu sˇc´ıt´an´ı alespoˇ n tolik hlas˚ u jako kandid´at druh´y? Tj. poloˇzili jsme a = b a k = 1. D´ale jsme zmˇenili podm´ınku z (ostˇre) ” v´ıc“ na alespoˇ n tolik“ a nept´ame se na pravdˇepodobnost, n´ ybrˇz na poˇcet vˇsech ” uspoˇra´d´an´ı. Necht’ n je poˇcet hlas˚ u, kter´e dostal kaˇzd´ y z kandid´at˚ u, a Cn ˇreˇsen´ı u ´lohy. Posloupnost hlas˚ u m˚ uˇzeme opˇet zn´azorˇ novat jako cestu ve ˇctvercov´e s´ıti. Cn je tedy poˇcet cest z [0, 0] do [2n, 0], kter´e nikdy neklesnou pod osu x. D´ale plat´ı, ˇze Cn−1 je poˇcet cest z [0, 0] do [2n, 0], kter´e nikdy neklesnou pod osu x a dotknou se j´ı pouze v krajn´ıch bodech. Proˇc? Protoˇze pro tyto cesty zˇrejmˇe plat´ı, ˇze jejich prvn´ı krok je nahoru, posledn´ı dol˚ u a zbyl´ ych n − 1 hlas˚ u pro A a n − 1 hlas˚ u pro B tvoˇr´ı cestu, kter´a nikdy neklesne pod pˇr´ımku y = 1. Zˇrejmˇe tedy plat´ı i to, ˇze Cn−1 je poˇcet cest z [0, 0] do [2n − 1, 1], kter´e se osy x dot´ ykaj´ı pouze v [0, 0]. Tento poˇcet uˇz ale zn´ame, viz (4.3), jedn´a se o p˚ uvodn´ı hlasovac´ı probl´em (pro a = n, b = n − 1). Chceme-li tedy spoˇc´ıtat Cn , dosad´ıme a = n + 1, b = n a dost´av´ame     1 2n + 1 1 (2n + 1)! (n + 1) − n (n + 1) + n Cn = = = · = (n + 1) + n n+1 2n + 1 n + 1 2n + 1 (n + 1)!n!   1 (2n)! 1 2n = · = . n + 1 n!n! n+1 n

43

  1 2n A pr´avˇe jako Cn = je definov´ano n-t´e Catalanovo ˇc´ıslo (pro vˇsechn+1 n na nez´aporn´a cel´a ˇc´ısla n). Nˇekolik prvn´ıch hodnot Cn ukazuje tabulka 4.1. Na Catalanova ˇc´ısla vede velk´e mnoˇzstv´ı kombinatorick´ ych probl´em˚ u. Asi dvˇe stˇe jich lze nal´ezt ve [27]. Napˇr. Cn je poˇcet vˇsech (n − 1)-prvkov´ ych posloupnost´ı pˇrirozen´ ych ˇc´ısel a1 < a2 < · · · < an−1 splˇ nuj´ıc´ıch 1 ≤ ai ≤ 2i. (Pro n = 4 to jsou 1, 2, 3; 1, 2, 4; 1, 2, 5; 1, 2, 6; 1, 3, 4; 1, 3, 5; 1, 3, 6; 1, 4, 5; 1, 4, 6; 2, 3, 4; 2, 3, 5; 2, 3, 6; 2, 4, 5 a 2, 4, 6, coˇz odpov´ıd´a tomu, ˇze C4 = 14.) Dalˇs´ım pˇr´ıkladem m˚ uˇze b´ yt triangulace konvexn´ıho (n + 2)-´ uheln´ıku pomoc´ı jeho u ´hlopˇr´ıˇcek tak, aby se ˇza´dn´e dvˇe nekˇr´ıˇzily, viz obr´azek 4.8. Poˇcet takov´ ych triangulac´ı je tak´e pr´avˇe Cn . n Cn

0 1 2 3 4 5 6 1 1 2 5 14 42 132

Tabulka 4.1: Hodnoty Catalanov´ ych ˇc´ısel.

Obr´azek 4.8: Pˇr´ıklad probl´emu vedouc´ıho na Catalanova ˇc´ısla – triangulace (n + 2)-´ uheln´ıku bez kˇr´ıˇzen´ı u ´hlopˇr´ıˇcek, (n = 4).

44

´ 5. Uloha oˇ skolaˇ ck´ ach Nejsp´ıˇs budete souhlasit, ˇze potˇreba sdˇelit si navz´ajem nejˇzhavˇejˇs´ı novinky ze ˇzivota je u dˇevˇcat opravdu siln´a. A kaˇzd´e dvˇe kamar´adky si na sebe najdou chvilku, at’ uˇz jsou okoln´ı podm´ınky sebekomplikovanˇejˇs´ı. Snad pr´avˇe proto je n´asleduj´ıc´ı u ´loha situov´ana do prostˇred´ı d´ıvˇc´ı intern´atn´ı ˇskoly. ´ Uloha 27. Patn´act ˇskolaˇcek chod´ı na sv´e kaˇzdodenn´ı vych´azky, a to vˇzdy ve trojic´ıch. Jak se maj´ı rozdˇelit, aby bˇehem jednoho t´ydne ˇsly kaˇzd´e dvˇe alespoˇ n jednou pohromadˇe? Tuto u ´lohu, zn´amou jako Fifteen Schoolgirl Problem, pˇrivedl na svˇetlo svˇeta roku 1850 britsk´ y knˇez a matematik Thomas P. Kirkman. Ke vˇsem (sedmi) navz´ajem neisomorfn´ım ˇreˇsen´ım dospˇel v roce 1862 Woulhouse. Z´ajemce je nalezne v [6]. Naˇs´ım c´ılem bude uk´azat si, jak lze rozliˇcn´ ymi cestami dospˇet alespoˇ n k jednomu ˇreˇsen´ı.

5.1

Pˇ r´ımoˇ car´ eˇ reˇ sen´ı

Nejdˇr´ıv si uvˇedomme, ˇze zad´an´ı u ´lohy je ekvivalentn´ı poˇzadavku, aby spolu ˇsly kaˇzd´e dvˇe d´ıvky pr´avˇe jednou, nebo tak´e nejv´ yˇse jednou, protoˇze kaˇzd´a d´ıvka m´a ˇctrn´act spoluˇzaˇcek a kaˇzd´ y ze sedmi dn´ı jde se dvˇema z nich. Naˇs´ım c´ılem je vytvoˇrit t´ ydenn´ı rozpis vych´azek tak, aby kaˇzd´ y den ˇsla kaˇzd´a d´ıvka v jedn´e z trojic a aby se bˇehem t´ ydne vyskytla kaˇzd´a dvojice pr´avˇe jednou, viz napˇr. tabulka 5.1. ´ ˇ Po Ut St Ct P´a So Ne 1, 2, 3 1, 4, 5 1, 6, 7 1, 8, 9 1, 10, 11 1, 12, 13 1, 14, 15 4, 8, 12 2, 9, 11 2, 8, 10 3, 5, 7 3, 4, 6 2, 5, 6 2, 4, 7 5, 10, 14 3, 13, 15 3, 12, 14 2, 13, 14 2, 12, 15 3, 9, 10 3, 8, 11 6, 9, 15 6, 8, 14 4, 9, 13 4, 10, 15 5, 8, 13 4, 11, 14 5, 9, 12 7, 11, 13 7, 10, 12 5, 11, 15 6, 11, 12 7, 9, 14 7, 8, 15 6, 10, 13 Tabulka 5.1: Uk´azka ˇreˇsen´ı u ´lohy o ˇskolaˇck´ach. Aˇc je zad´an´ı velmi prost´e, naj´ıt ˇreˇsen´ı nen´ı u ´plnˇe jednoduch´e. Je celkem pˇrirozen´e pokouˇset se vytvoˇrit vhodn´ y rozpis metodou pokus – omyl s jistou d´avkou systematiˇcnosti. Bez vhodn´e myˇslenky se to ale nemus´ı hned podaˇrit. (Necht’ se ˇcten´aˇr chop´ı pap´ıru a tuˇzky a s´am se o tom pˇresvˇedˇc´ı.) Zde si uk´aˇzeme Frostovo ˇreˇsen´ı uveden´e v [8]. Vyplˇ nujeme tabulku o sedmi sloupc´ıch. Jednu d´ıvku pevnˇe zvol´ıme (oznaˇcme ji x) a um´ıst´ıme na prvn´ı ˇra´dek v kaˇzd´em sloupci. D´ıvky, kter´e jdou s x, oznaˇc´ıme postupnˇe a1 , a2 , b1 , b2 , . . . , g1 , g2 . M´ame tedy: ´ ˇ Po Ut St Ct P´a So Ne xa1 a2 xb1 b2 xc1 c2 xd1 d2 xe1 e2 xf1 f2 xg1 g2

45

D´ale budeme pracovat bez index˚ u 1 a 2 a z p´ısmen a, b, . . . , g sestav´ıme trojice tak, aby se kaˇzd´a dvojice vyskytovala pr´avˇe jednou. To je vzhledem k mal´emu poˇctu prvk˚ u trivi´aln´ı. Dostaneme trojice abc, ade, af g, bdf , beg, cdg, cef . Kaˇzdou z trojic um´ıst´ıme do tˇech ˇctyˇr sloupc˚ u tabulky, kde se v prvn´ım ˇr´adku nevyskytuje ˇza´dn´e z jej´ıch p´ısmen, viz tabulka 5.2. ´ ˇ Ut Ct Po St P´a So Ne xa1 a2 xb1 b2 xc1 c2 xd1 d2 xe1 e2 xf1 f2 xg1 g2 bdf ade ade abc abc abc abc beg af g af g af g af g ade ade cdg cdg bdf beg bdf beg bdf cef cef beg cef cdg cdg cef Tabulka 5.2: Frostovo ˇreˇsen´ı – pˇred pˇriˇrazen´ım index˚ u. Vid´ıme, ˇze zb´ yv´a p´ısmen˚ um vhodnˇe pˇriˇradit indexy 1 nebo 2. To provedeme nejdˇr´ıv pro vˇsechny v´ yskyty trojice bdf , potom pro vˇsechny v´ yskyty beg atd. (trojice bereme podle jejich poˇrad´ı v tabulce). Pˇri tom se ˇr´ıd´ıme tˇemito pravidly: • V jednom sloupci nesm´ı b´ yt pro dan´e p´ısmeno pouˇzit dvakr´at stejn´ y index. ˇ adn´a dvojice (indexovan´ • Z´ ych p´ısmen) spolu nesm´ı b´ yt v´ıcekr´at. • Pokud prvn´ı dvˇe pravidla neurˇc´ı index jednoznaˇcnˇe, indexujeme ˇc´ıslem 1. T´ım je u ´loha vyˇreˇsena, viz tabulka 5.3. Pouˇzijeme-li pro oznaˇcen´ı d´ıvek ˇc´ısla m´ısto p´ısmen (x = 1, a1 = 2, a2 = 3, . . . , g2 = 15), dostaneme rozpis uveden´ y na zaˇc´atku kapitoly (tab. 5.1). ´ ˇ Po Ut St Ct P´a So Ne xa1 a2 xb1 b2 xc1 c2 xd1 d2 xe1 e2 xf1 f2 xg1 g2 b1 d1 f1 a1 d2 e2 a1 d1 e1 a2 b2 c2 a2 b1 c1 a1 b2 c1 a1 b1 c2 b2 e1 g1 a2 f2 g2 a2 f1 g1 a1 f2 g1 a1 f1 g2 a2 d2 e1 a2 d1 e2 c1 d2 g2 c1 d1 g1 b1 d2 f2 b1 e1 g2 b2 d1 f2 b1 e2 g1 b2 d2 f1 c2 e2 f2 c2 e1 f1 b2 e2 g2 c1 e2 f1 c2 d2 g1 c2 d1 g2 c1 e1 f2 Tabulka 5.3: Frostovo ˇreˇsen´ı – koneˇcn´a podoba.

5.2

Algebraick´ eˇ reˇ sen´ı

N´asleduj´ıc´ı ˇreˇsen´ı je tak´e moˇzn´e naj´ıt v [8]. Jednu d´ıvku (?) opˇet pevnˇe zafixujeme a ostatn´ı rozdˇel´ıme do dvou skupin. V obou skupin´ach oˇc´ıslujeme d´ıvky 0 aˇz 6. V n´asleduj´ıc´ım textu budeme oznaˇcovat d´ıvky prvn´ı skupiny mal´ ymi p´ısmeny a druh´e velk´ ymi. Pracovat budeme v tˇelese Z7 . Pokus´ıme se naj´ıt rozdˇelen´ı d´ıvek, kter´e pro r-t´ y den (r = 0 pro pondˇel´ı,. . . , r = 6 pro nedˇeli) vypad´a n´asledovnˇe:

46

a+r α+r b+r β+r c+r γ+r d+r ? E+r F +r

A+r B+r C +r D+r G+r

D´ıky tomu, ˇze se r kaˇzd´ y den nav´ yˇs´ı o jedniˇcku, dostane se kaˇzd´a z d´ıvek pr´avˇe jednou bˇehem t´ ydne na kaˇzdou z pozic svoj´ı skupiny. D´ıvky z prvn´ı skupiny se ˇ ısla navz´ajem potk´avaj´ı na prvn´ıch tˇrech ˇr´adc´ıch v prvn´ıch dvou sloupc´ıch. C´ kaˇzd´ ych dvou d´ıvek se navzd´ajem liˇs´ı o 1, 2 nebo 3. A kaˇzd´e dvˇe se mus´ı setkat. To n´am zaruˇc´ı podm´ınky α − a = 1,

β − b = 2,

γ − c = 3.

(5.1)

Podobnˇe se d´ıvky z druh´e skupiny potk´avaj´ı na posledn´ım ˇra´dku, pokaˇzd´e tˇri najednou. Ze stejn´ ych d˚ uvod˚ u jako v´ yˇse budeme poˇzadovat F − E = 1,

G − F = 2,

G − E = 3.

(5.2)

Zb´ yv´a n´am zajistit kontakty mezi d´ıvkami z r˚ uzn´ ych skupin. Rozd´ıl ˇc´ısla d´ıvky z druh´e skupiny a ˇc´ısla d´ıvky ze skupiny prvn´ı je 0 aˇz 6. Aby se setkaly kaˇzd´e dvˇe, mus´ı platit {A − a, A − α, B − b, B − β, C − c, C − γ, D − d} = {0, 1, 2, 3, 4, 5, 6}. (5.3) Nyn´ı se budeme snaˇzit splnit vˇsechny v´ yˇse uveden´e podm´ınky. Jde to aˇz pˇrekvapivˇe snadno. Nejdˇr´ıv rozestav´ıme d´ıvky z prvn´ı skupiny tak, aby platilo (5.1). D´ale um´ıst´ıme d´ıvky do sloupeˇcku vpravo a snaˇz´ıme se vyhovˇet (5.3). Zbydou n´am ˇc´ısla 3, 4 a 6, kter´e, k naˇs´ı radosti a spokojenosti, splˇ nuj´ı (5.2). 0 1 0 0 a α A 0 1 2 4 2 4 5 2 b β B 3 6 3 6 1 3 c γ C 5 ? d ? D 5 ? 2 5 3 E F G ´ Uloha je tedy vyˇreˇsena. Na z´avˇer uvedeme rozpis vych´azek na (d´ıvky prvn´ı skupiny pˇreznaˇc´ıme na a0 , . . . , a6 a druh´e b0 , . . . , b6 ). Po a0 a1 b 0 a2 a4 b 5 a3 a6 b 1 a5 ? b 2 b3 b4 b6

´ Ut a1 a2 b 1 a3 a5 b 6 a4 a0 b 2 a6 ? b 3 b4 b5 b 0

St a2 a3 b 2 a4 a6 b 0 a5 a1 b 3 a0 ? b 4 b 5 b6 b1

ˇ Ct a3 a4 b3 a5 a0 b1 a6 a2 b4 a1 ? b 5 b6 b0 b2

P´a a4 a5 b 4 a6 a1 b 2 a0 a3 b 5 a2 ? b 6 b0 b1 b3

So a5 a6 b5 a0 a2 b3 a1 a4 b6 a3 ? b 0 b1 b2 b4

Ne a6 a0 b 6 a1 a3 b 4 a2 a5 b 0 a4 ? b 1 b2 b 3 b5

Tabulka 5.4: Algebraick´e ˇreˇsen´ı – koneˇcn´a podoba.

47

1 0 4 5 6 1 ? 2 4 6 cel´ y t´ yden

5.3

Geometrick´ aˇ reˇ sen´ı – krychle a ˇ ctyˇ rstˇ en

Zaj´ımav´ ym pohledem na u ´lohu o ˇskolaˇck´ach je pohled geometrick´ y. Z´akladn´ım principem je zvolit strukturu, kter´a m´a 15 prvk˚ u, jeˇz odpov´ıdaj´ı jednotliv´ ym d´ıvk´am, a pˇri konstrukci ˇreˇsen´ı pak vyuˇz´ıvat r˚ uzn´e symetrie mezi nimi. Nejdˇr´ıve si uk´aˇzeme ˇreˇsen´ı za pomoci krychle poch´azej´ıc´ı z [7]. Zde si ho pˇredevˇs´ım obohat´ıme o n´azorn´e obr´azky. Jak jde krychle a hodnota 15 dohromady? Inu, osm vrchol˚ u, ˇsest stˇen a krychle sama. Pro n´azornost bude nejjednoduˇsˇs´ı ztotoˇznit d´ıvky s vrcholy krychle, stˇredy stˇen a stˇredem krychle tak, jak je uk´az´ano na obr´azku 5.1.

Obr´azek 5.1: D´ıvky odpov´ıdaj´ı zn´azornˇen´ ym bod˚ um krychle. Budeme postupovat ve dvou kroc´ıch. Nejdˇr´ıve vytvoˇr´ıme trojice, kter´e splˇ nuj´ı podm´ınku, ˇze kaˇzd´e dvˇe d´ıvky jsou spolu pr´avˇe jednou. Ve druh´em kroku uk´aˇzeme, jak je moˇzn´e rozm´ıstit tyto trojice do sedmi dn˚ u. V tomto ˇreˇsen´ı se objev´ı n´asleduj´ıc´ı typy trojic (viz obr. 5.2): • stˇred krychle a dva protilehl´e vrcholy (typ a) • stˇred krychle a stˇredy dvou protˇejˇs´ıch stˇen (typ b) • dva sousedn´ı vrcholy a stˇred pˇrilehl´e stˇeny (typ c) • stˇredy tˇr´ı sousedn´ıch stˇen (typ d) • dva protˇejˇs´ı vrcholy jedn´e stˇeny a stˇred stˇeny protˇejˇs´ı (typ e)

Obr´azek 5.2: Typy utv´aˇren´ ych trojic, postupnˇe a aˇz e. Co se t´ yˇce trojic typ˚ u a, b a e, je situace jednoduch´a – vezmeme vˇsechny moˇzn´e trojice dan´eho typu (tj. ˇctyˇri a, tˇri b a dvan´act e). V pˇr´ıpadˇe typu c zvol´ıme 48

12 z 24 moˇznost´ı. Pro kaˇzd´e dva sousedn´ı vrcholy je potˇreba zvolit jednu ze dvou stˇen, s jej´ımˇz stˇredem budou tvoˇrit trojici. (Kdyby tvoˇrily trojice se stˇredy obou stˇen, vyskytovaly by se tyto dva vrcholy spolu dvakr´at, coˇz nechceme.) Trojice vybereme tak, jak je zn´azornˇeno na obr´azku 5.3 – za trojici vol´ıme vrcholy kaˇzd´eho z modr´ ych troj´ uheln´ık˚ u (symetricky pro zakrytou ˇca´st krychle). Podobnˇe pro typ d je potˇreba vybrat 4 z 8 moˇznost´ı tak, aby se stˇredy ˇza´dn´ ych dvou stˇen spolu nevyskytovaly v´ıcekr´at. V´ ybˇer provedeme podle obr´azku 5.4 – kaˇzd´a trojice je urˇcena jedn´ım vrcholem krychle (modr´ y). Vybereme trojice pˇr´ısluˇsej´ıc´ı zv´ yraznˇen´ ym vrchol˚ um.

Obr´azek 5.3: Volba trojic typu c.

Obr´azek 5.4: Volba trojic typu d.

Celkem jsme z´ıskali 4 + 3 + 12 + 12 + 4 = 35 trojic. Nen´ı tˇeˇzk´e ovˇeˇrit, ˇze se ˇza´dn´a dvojice spolu nevyskytuje v´ıcekr´at, takˇze prvn´ı krok je splnˇen. Nyn´ı zb´ yv´a rozdˇelit pˇr´ısluˇsn´e trojice do sedmi dn´ı. Pro pondˇel´ı aˇz ˇctvrtek vybereme vˇzdy jednu trojici typu a, jednu typu d a tˇri typu c, pˇriˇcemˇz pro danou trojici typu a je zbytek v´ ybˇeru jednoznaˇcn´ y. P´atku aˇz nedˇeli bude n´aleˇzet jedna trojice typu b a k n´ı ˇctyˇri pˇr´ısluˇsej´ıc´ı trojice typu e. Zde si m˚ uˇzeme vybrat jednu ze dvou moˇznost´ı, jak budou zkombinov´any. (Pro pˇrehlednost budeme trojici typu e zn´azorˇ novat tak, jak je uk´az´ano na obr´azku 5.5.) V´ ysledn´e ˇreˇsen´ı ukazuje obr´azek 5.6.

Obr´azek 5.5: Zjednoduˇsen´e zn´azorˇ nov´an´ı trojice typu e.

ˇ druh´a P´a Obr´azek 5.6: Rozvrˇzen´ı do dn˚ u – prvn´ı krychle zn´azorˇ nuje Po aˇz Ct, aˇz Ne, tˇret´ı je alternativou ke druh´e (tj. vol´ıme jednu z nich). 49

ˇ sen´ı poch´az´ı z [9], kde lze Obdobnˇe jako krychli je moˇzn´e vyuˇz´ıt i ˇctyˇrstˇen. Reˇ ˇ naj´ıt podrobnosti. Ctyˇrstˇen m´a ˇctyˇri stˇeny, ˇctyˇri vrcholy, ˇsest hran a s´am sebe. Pˇr´ısluˇsn´e trojice opˇet utvoˇr´ıme pomˇernˇe pˇrirozen´ ym zp˚ usobem (pro n´azornost viz obr. 5.7 a 5.8): • dva vrcholy a hrana, kter´a je spojuje (typ a) • vrchol, hrana, kter´a v nˇem nezaˇc´ın´a, a stˇena, jiˇz maj´ı spoleˇcnou (typ b) • tˇri hrany pˇr´ısluˇsej´ıc´ı jedn´e stˇenˇe (typ c) • vrchol, protˇejˇs´ı stˇena a ˇctyˇrstˇen s´am (typ d) • dvˇe nesousedn´ı hrany a ˇctyˇrstˇen s´am (typ e) • hrana a dvˇe stˇeny, kter´e s n´ı nesoused´ı (typ f )

ˇ rstˇen – typy utv´aˇren´ Obr´azek 5.7: Ctyˇ ych trojic, zleva doprava a aˇz f .

ˇ rstˇen – zjednoduˇsen´e zn´azornˇen´ı trojic, zleva doprava a aˇz f . Obr´azek 5.8: Ctyˇ V pˇr´ıpadˇe ˇctyˇrstˇenu je situace jednoduch´a – do v´ ybˇeru zaˇrazujeme vˇsechny existuj´ıc´ı trojice dan´ ych typ˚ u. To je celkem ˇsest trojic typu a, dvan´act b, ˇctyˇri c, ˇctyˇri d, tˇri e a ˇsest f . Vid´ıme, ˇze dohromady d´avaj´ı potˇrebn´ ych 35 trojic a snadno 50

dok´aˇzeme ovˇeˇrit, ˇze se spolu ˇza´dn´a dvojice nevyskytuje v´ıcekr´at. Zb´ yv´a tedy prov´est rozdˇelen´ı do jednotliv´ ych dn˚ u. Pro pondˇel´ı aˇz ˇctvrtek vyuˇzijeme vˇzdy jednu trojici typu c, jednu d a tˇri b, pro p´atek aˇz nedˇeli dvˇe a, jednu e a dvˇe f , jak je uk´az´ano na obr´azku 5.9.

ˇ druh´ Obr´azek 5.9: Rozvrˇzen´ı do dn˚ u – prvn´ı ˇctyˇrstˇen zn´azorˇ nuje Po aˇz Ct, y P´a aˇz Ne. Jeˇstˇe si uved’me, jak mohou vypadat rozpisy vych´azek na z´akladˇe zde zm´ınˇen´ ych ˇreˇsen´ı. Jeden pro krychli, jeden pro ˇctyˇrstˇen. Odpov´ıdaj´ı jim tabulky 5.5 a 5.6, priˇcemˇz d´ıvky jsou oˇc´ıslov´any podle obr´azku 5.10. 9 8 15 5

6

13 14 5

1

11

7 9

12 4

11 10

2

2

15 8 1 13 12

4 14 10 7

6 3

3

Obr´azek 5.10: Oznaˇcen´ı d´ıvek – krychle a ˇctyˇrstˇen. ´ ˇ Po Ut St Ct P´a So Ne 1, 5, 7 1, 4, 6 1, 3, 9 1, 2, 8 1, 11, 13 1, 12, 14 1, 10, 15 2, 3, 10 2, 5, 14 2, 6, 11 3, 4, 12 2, 9, 12 2, 4, 15 2, 7, 13 4, 8, 13 3, 7, 11 4, 5, 10 5, 9, 13 3, 5, 15 3, 6, 13 3, 8, 14 6, 9, 14 8, 9, 15 7, 8, 12 6, 7, 15 4, 7, 14 5, 8, 11 4, 9, 11 11, 12, 15 10, 12, 13 13, 14, 15 10, 11, 14 6, 8, 10 7, 9, 10 5, 6, 12 Tabulka 5.5: Rozpis podle ˇreˇsen´ı vyuˇz´ıvaj´ıc´ıho krychli.

51

´ ˇ Ut Ct Po St P´a So Ne 1, 5, 12 1, 2, 14 1, 3, 15 1, 4, 13 1, 7, 9 1, 8, 10 1, 6, 11 2, 10, 13 3, 9, 13 2, 7, 12 2, 11, 15 2, 3, 6 2, 5, 9 2, 4, 8 3, 11, 14 4, 6, 12 4, 10, 14 3, 8, 12 4, 5, 11 3, 4, 7 3, 5, 10 4, 9, 15 5, 8, 15 5, 6, 13 5, 7, 14 8, 13, 14 6, 14, 15 7, 13, 15 6, 7, 8 7, 10, 11 8, 9, 11 6, 9, 10 10, 12, 15 11, 12, 13 9, 12, 14 Tabulka 5.6: Rozpis podle ˇreˇsen´ı vyuˇz´ıvaj´ıc´ıho ˇctyˇrstˇen.

5.4

Geometrick´ eˇ reˇ sen´ı – pyramida

Po zhl´ednut´ı v´ yˇse uveden´ ych ˇreˇsen´ı je zaj´ımav´e zapˇrem´ yˇslet, jak´a dalˇs´ı struktura by se dala vyuˇz´ıt, a pokusit se naj´ıt vlastn´ı zp˚ usob ˇreˇsen´ı. Nejdˇr´ıv n´as mohou napadat ostatn´ı plat´onsk´a tˇelesa∗ . Dvan´actistˇen a dvacetistˇen jsou ale pro naˇse u ´ˇcely pˇr´ıliˇs velk´e“. Osmistˇen by se pouˇz´ıt dal, ale vzhledem k tomu, ˇze je du´aln´ı s ” krychl´ı (krychle m´a ˇsest stˇen a osm vrchol˚ u, osmistˇen naopak), nebyl by v´ ysledek nijak zaj´ımav´ y. Nuˇze, zkusme to jinak. Kde jinde je moˇzn´e naj´ıt patn´actku? Napˇr. zde: 1 + 2 + 3 + 4 + 5 = 15. A dvourozmˇern´a pyramida je na svˇetˇe! (Viz obr. 5.11.)

Obr´azek 5.11: Pyramida z patn´acti prvk˚ u. Na kaˇzd´e koleˇcko se m˚ uˇzeme d´ıvat jako na jednu ˇskolaˇcku. Trojice d´ıvek jdouc´ıch spoleˇcnˇe obarvujeme tout´eˇz barvou. Na rozd´ıl od krychle nebo ˇctyˇrstˇenu nebudeme nejdˇr´ıv hledat rozdˇelen´ı do trojic a ty pak rozvrhovat do dn˚ u, n´ ybrˇz se budeme pˇr´ımo snaˇzit konstruovat rozvrh pro dan´ y den. Hlavn´ı ideou je moˇznost dvakr´at po sobˇe otoˇcit pyramidu o 120 stupˇ n˚ u na sebe samu. Neobarv´ıme-li v pyramidˇe jednou barvou ˇz´adnou trojici koleˇcek, kter´a se navz´ajem ot´aˇc´ı na sebe, m˚ uˇzeme stejn´ y zp˚ usob obarven´ı pouˇz´ıt tˇri dny za sebou, coˇz je pˇresnˇe to, co n´am usnadn´ı pr´aci pˇri hled´an´ı ˇreˇsen´ı. Pyramida je tak´e osovˇe soumˇern´a, coˇz m˚ uˇzeme intuitivnˇe vyuˇz´ıt pˇri obarvov´an´ı. Snaˇz´ıme se tedy dospˇet k tomu, aby pondˇel´ı aˇz stˇreda a ˇctvrtek aˇz sobota byly utvoˇreny pomoc´ı jednoho obarven´ı. Jedno u ´spˇeˇsn´e ˇreˇsen´ı je uk´az´ano na obr. 5.12. Rozpis vych´azek dan´ y t´ımto ˇreˇsen´ım pˇri oˇc´ıslov´an´ı podle obr´azku 5.13 zn´azorˇ nuje tabluka 5.7.

∗

Plat´ onsk´e tˇeleso je pravideln´ y konvexn´ı mnohostˇen. Existuje jich celkem pˇet – ˇctyˇrstˇen, ˇsestistˇen (krychle), osmistˇen, dvan´actistˇen a dvacetistˇen.

52

Obr´azek 5.12: V´ ysledn´e ˇreˇsen´ı pomoc´ı pyramidy.

1 2 4 7 11

3 5

8 12

6 9

13

10 14

15

Obr´azek 5.13: Oznaˇcen´ı d´ıvek – pyramida.

´ ˇ Po Ut St Ct P´a So Ne 1, 2, 3 1, 9, 14 1, 8, 12 1, 5, 13 1, 4, 10 1, 6, 7 1, 11, 15 4, 5, 6 2, 5, 15 2, 4, 7 2, 8, 10 2, 9, 12 2, 11, 13 2, 6, 14 7, 8, 15 3, 6, 10 3, 5, 11 3, 7, 9 3, 13, 15 3, 8, 14 3, 4, 12 9, 10, 11 4, 8, 13 6, 9, 13 4, 11, 14 5, 7, 14 4, 9, 15 5, 8, 9 12, 13, 14 7, 11, 12 10, 14, 15 6, 12, 15 6, 8, 11 5, 10, 12 7, 10, 13 Tabulka 5.7: Rozpis podle ˇreˇsen´ı vyuˇz´ıvaj´ıc´ıho pyramidu.

53

5.5

´ Uloha o golfistech a Schurigovy tabulky

Nyn´ı zm´ın´ıme jedno moˇzn´e zobecnˇen´ı u ´lohy o ˇskolaˇck´ach. V origin´ale se naz´ yv´a Social Golfer Problem. ´ Uloha 28. Celkem s · h golfist˚ u hraje jedenkr´at t´ydnˇe golf v s skupin´ach po h hr´aˇc´ıch. Mohou hr´at t t´ydn˚ u, aniˇz by se spolu nˇekteˇr´ı dva setkali v´ıc neˇz jednou? Nejdˇr´ıv poznamenejme, ˇze tento probl´em je st´ale otevˇren´ y, ˇreˇsen´ı je zn´am´e jen pro nˇekter´e jeho instance. Jednou z nich je pr´avˇe u ´loha o ˇskolaˇck´ach (s = 5, h = 3, t = 7). Zpravidla je c´ılem naj´ıt nejvˇetˇs´ı moˇzn´e t pro dan´a s a h. Je snadn´e odhadnout t shora. Bˇehem kaˇzd´eho z t t´ ydn˚ u hraje kaˇzd´ y hr´aˇc s h−1 dalˇs´ımi a celkov´ y poˇcet tˇech, se kter´ ymi hraje, nem˚ uˇze pˇres´ahnout poˇcet vˇsech hr´aˇc˚ u (bez nˇeho sam´eho). Odtud t · (h − 1) ≤ s · h − 1, ˇcili t ≤ (s · h − 1)/(h − 1).

(5.4)

P˚ uvodn´ı ot´azka, poloˇzen´a v kvˇetnu 1998 (viz [30]), se ptala konkr´etnˇe na 32 golfist˚ u ve skupin´ach po ˇctyˇrech. Z´ahy bylo nalezeno ˇreˇsen´ı pro t = 9. Zˇrejmˇe t < 11, takˇze zb´ yvalo zodpovˇedˇet, zda lze t = 10. Roku 2004 dok´azal A. Aguado, ˇze ano, viz [1]. ˇ sen´ı dalˇs´ıch instanc´ı probl´emu uv´ad´ı napˇr. [17]. Odtud poch´az´ı i tabulka 5.8, Reˇ kter´a ukazuje maxim´aln´ı moˇzn´e t pro kombinace nˇekter´ ych hodnot s a h. Zde si m˚ uˇzeme povˇsimnout jedn´e skuteˇcnosti. Napˇr´ıklad pro 12 hr´aˇc˚ u hraj´ıc´ıch ve ˇctyˇrech skupin´ach po tˇrech je nejvyˇsˇs´ı dosaˇziteln´e t rovno ˇctyˇrem, aˇckoliv bychom podle (5.4) mohli doufat v ˇreˇsen´ı, kde t = 5. Odtud vid´ıme, ˇze nem˚ uˇzeme b´ yt pˇr´ıliˇs optimistiˇct´ı“, a pˇredpokl´adat, ˇze vˇzdy existuje ˇreˇsen´ı dan´e naˇs´ım horn´ım ” odhadem. Skupin 4 5 6 7 8 9

Hr´aˇc˚ u ve 2 3 7 4 9 7 11 8 13 10 15 11 17 13

sk. 4 5 5 7 9 10 11

Tabulka 5.8: Pˇrehled toho, kolikr´at mohou golfist´e hr´at v dan´em poˇctu skupin o dan´e velikosti, aniˇz by se nˇekteˇr´ı dva potkali v´ıcekr´at. Z´avˇerem jeˇstˇe zmiˇ nme, ˇze za speci´aln´ı pˇr´ıpad u ´lohy o golfistech m˚ uˇzeme povaˇzovat napˇr. i ˇsachov´ y turnaj, kde soupeˇr´ı nepˇr´ıliˇs velk´ y sud´ y poˇcet hr´aˇc˚ u a poˇzaduje se, aby kaˇzd´ y s kaˇzd´ ym sehr´al pr´avˇe jednu partii (a pochopitelnˇe i to, aby v kaˇzd´em kole hr´ali vˇsichni u ´ˇcastn´ıci). Tj. m´ame h = 2 a chceme t = h · s − 1. ˇ Reˇsen´ı existuje vˇzdy a je velmi snadn´e jej zkonstruovat. Nejen ˇceˇst´ı ˇsachist´e za t´ımto u ´ˇcelem vyuˇz´ıvaj´ı tabulky, kter´e v devaten´act´em stolet´ı sestavil nˇemeck´ y matematik R. Schurig. Zp˚ usob jejich konstrukce i dalˇs´ı podrobnosti pˇrehlednˇe popisuje [32]. 54

Zde si uk´aˇzeme, jak dostat Schurigovu tabulku pro ˇsest hr´aˇc˚ u. A to i vˇcetnˇe toho, aby se jednotliv´ ym hr´aˇc˚ um, pokud moˇzno, stˇr´ıdaly kolo od kola b´ıl´e a ˇcern´e ’ kameny, byt to nen´ı poˇzadov´ano v naˇs´ı u ´loze. Analogick´ y postup lze pouˇz´ıt i pro jin´ y poˇcet hr´aˇc˚ u. Hr´aˇce oznaˇc´ıme ˇc´ısly 1 aˇz 6. Celkem sehraj´ı 5 kol, rozpis kaˇzd´eho kola bude na jednom ˇra´dku. V kaˇzd´em kole se spolu stˇretnou tˇri dvojice. V kaˇzd´e dvojici m´a b´ıl´e ten, kdo je naps´an na prvn´ım m´ıstˇe. V prvn´ım kroku budeme postupovat po ˇra´dc´ıch a ps´at ˇc´ısla 1 aˇz 5 (tj. ˇc´ıslo 6 vynech´av´ame). Po pˇetce vˇzdy pokraˇcujeme jedniˇckou, viz tabulka 5.9. 1. 2. 3. 4. 5.

kolo: kolo: kolo: kolo: kolo:

1 4 2 5 3

-

2 5 3 1 4

-

3 1 4 2 5

-

Tabulka 5.9: Schurigova tabulka pro 6 hr´aˇc˚ u – prvn´ı krok. Ve druh´em kroku si zakryjeme prvn´ı sloupec, nic do nˇej nepˇripisujeme. Opˇet postupujeme po ˇra´dc´ıch, ˇc´ısla tentokr´at p´ıˇseme v sestupn´em poˇrad´ı, od pˇetky k jedniˇcce, viz tabulka 5.10. 1. 2. 3. 4. 5.

kolo: kolo: kolo: kolo: kolo:

1 4 2 5 3

-

2 5 3 1 4

-

5 3 1 4 2

3 1 4 2 5

-

4 2 5 3 1

Tabulka 5.10: Schurigova tabulka pro 6 hr´aˇc˚ u – druh´ y krok. Nyn´ı uˇz jen zb´ yv´a doplnit do prvn´ıho sloupce ˇc´ıslo 6. Kv˚ uli stˇr´ıd´an´ı barev je v sud´ ych kolech uvedeno na prvn´ım m´ıstˇe. V´ ysledek ukazuje tabulka 5.11. 1. 2. 3. 4. 5.

kolo: kolo: kolo: kolo: kolo:

1-6 6-4 2-6 6-5 3-6

2 5 3 1 4

-

5 3 1 4 2

3 1 4 2 5

-

4 2 5 3 1

Tabulka 5.11: Schurigova tabulka pro 6 hr´aˇc˚ u – hotovo. Jeˇstˇe si ukaˇzme, ˇze Schurigova tabulka opravdu funguje“, tj. kaˇzd´a dvojice se ” stˇretne. Pro 2k hr´aˇc˚ u m´a tabulka 2k − 1 ˇra´dk˚ u (kol) a k sloupc˚ u (stol˚ u). Ptejme se, kdo hraje v r-t´em kole na s-t´em stole (kromˇe prvn´ıho, kter´ y se obsazuje jin´ ym zp˚ usobem). Necht’ b je ˇc´ıslo hr´aˇce hraj´ıc´ıho s b´ıl´ ymi kameny, c s ˇcern´ ymi. (Zab´ yv´ame se vˇsemi hr´aˇci kromˇe 2k.) Ze zp˚ usobu, jak je tabulka tvoˇrena nen´ı tˇeˇzk´e odvodit, ˇze b ≡ (r − 1)k + s c ≡ −((r − 1)(k − 1) + (s − 1)) + 1, 55

pˇriˇcemˇz v tˇechto i n´asleduj´ıc´ıch kongruenc´ıch poˇc´ıt´ame (mod 2k − 1). Odtud po u ´prav´ach d´ale dost´av´ame b ≡ rk − k + s c ≡ −rk + k − s + r + 1 b + c ≡ r + 1.

(5.5)

V´ ysledek (5.5) n´am ˇr´ık´a pˇredevˇs´ım to, ˇze pokud spolu dva hr´aˇci v pr˚ ubˇehu turnaje hraj´ı, pak je jednoznaˇcnˇe urˇceno, ve kter´em kole. (Zde je potˇreba vz´ıt do u ´vahy i to, ˇze ze zp˚ usobu odvozen´ı (5.5) vypl´ yv´a, ˇze plat´ı pro obˇe moˇznosti toho, jak´e barvy kamen˚ u maj´ı hr´aˇci. Vznik´a totiˇz seˇcten´ım dvou kongruentn´ıch rovnic, a kdybychom v nich zamˇenili b a c, dostali bychom tot´eˇz.) D´ale si uvˇedom´ıme, ˇze (5.5) splˇ nuje pr´avˇe k − 1 dvojic r˚ uzn´ ych ˇc´ısel z 1, . . . , 2k − 1. To odpov´ıd´a tomu, ˇze v kaˇzd´em kole je takto obsazeno k − 1 stol˚ u (prvn´ı uvaˇzujeme zvl´aˇst’). Potˇrebujeme ale jeˇstˇe ovˇeˇrit, ˇze se na ˇz´adn´em ˇra´dku nevyskytuje ˇza´dn´a dvojice v´ıcekr´at. K tomu n´am pom˚ uˇze o nˇeco silnˇejˇs´ı tvrzen´ı. Uk´aˇzeme, ˇze hr´aˇc hraj´ıc´ı v r-t´em kole na posledn´ım stole s ˇcern´ ymi, oznaˇcme jej x, je tent´ yˇz jako hr´aˇc na prvn´ım stole v (r + 1)-n´ım kole. (M˚ uˇzeme uvaˇzovat, ˇze n´asleduj´ıc´ım kolem k posledn´ımu je prvn´ı.) Z toho pak plyne, ˇze v prvn´ım kroku tvorby tabulky bylo na r-t´ y ˇr´adek naps´ano k ˇc´ısel pˇredch´azej´ıc´ıch x a ve druh´em kroku x a k − 2 ˇc´ısel n´asleduj´ıc´ıch. Kaˇzd´e ˇc´ıslo se tedy na ˇr´adku vyskytuje pr´avˇe jednou, a tud´ıˇz se ˇza´dn´a dvojice nem˚ uˇze objevit v´ıcekr´at. Oznaˇcme hr´aˇce na prvn´ım stole v (r + 1)-n´ım kole jako y a dokaˇzme, ˇze x = y. Pro dan´e r opˇet m˚ uˇzeme vypoˇc´ıtat, o koho pˇresnˇe se jedn´a: x ≡ −((r − 1)(k − 1) + (k − 1)) + 1 y ≡ ((r + 1) − 1)k + 1 A po u ´prav´ach x ≡ −r(k − 1) + 1 y ≡ rk + 1 y − x ≡ r(2k − 1) y − x ≡ 0.

(5.6)

Vzhledem k tomu, ˇze ˇc´ısla hr´aˇc˚ u jsou mezi 1 a 2k − 1, z (5.6) plyne x = y. Platnost“ Schurigov´ ych tabulek uˇz jsme tedy uk´azali pro vˇsechny stoly vyjma ” prvn´ıho. Tam je ale situace jednoduch´a. Snadno m˚ uˇzeme domyslet, ˇze se na nˇem kaˇzd´ y z 2k − 1 hr´aˇc˚ u objev´ı pr´avˇe jednou a utk´a se s hr´aˇcem 2k. T´ım jsme hotovi. A pozitivn´ı nav´ıc je, ˇze na z´akladˇe zjiˇstˇen´ı, kter´a jsme vyuˇzili k d˚ ukazu, dok´aˇzeme bez toho, abychom si vypsali celou tabulku, ˇr´ıct, ve kter´em kole se stˇretnou dan´ı dva hr´aˇci, nebo domyslet, jak vypad´a jej´ı ˇra´dek pro dan´e kolo.

56

Z´ avˇ er Z´avˇerem si pˇripomeˇ nme, s jak´ ymi u ´lohami jsme se sezn´amili. Aneb co bychom byli za kombinatoriky, kdybychom vˇsechno nezkombinovali?

T

U A B

S

C D

R Q P O

E F G H N

M L K J

J A

H

E va Z denda O lga

I

O N

S tanda A nna

Norbert + Anna Radek + Ema Standa + Olga Zdenda + Iva Zikmund + Eva

I va

E ma ?

57

A) AABAAB B) AAABBA C) AAAABB D) AABABA E) AABBAA F) AAABAB ´ Po Ut BEN DEJ MLJ ... ... MNO ... ... ... ...

ˇ St P´a So Ne Ct LOK DIK HEK FOG KAM ... ... ... ... BIL ... H?N . . . LCD ... FIN ... MCF . . . ... ... AJO . . . ... ...

1. Kdo pˇreˇzije? 2. Kter´ y kotouˇc se pohne? 3. Kdo sed´ı mezi Ivou a Emou? 4. Kter´a posloupnost nen´ı dobr´a? 5. Kdo jde na vych´azku spoleˇcnˇe s H a N ?

A TO JE

58

Seznam pouˇ zit´ e literatury [1] Aguado, A. A 10 Days Solution to the Social Golfer Problem. 2004. [Citov´ano 26. bˇrezna 2012]. Dostupn´e z: http://www.maa.org/editorial/mathgames/socgolf1.pdf [2] Bogart, K. P. – Doyle, P. G. Non-sexist Solution of the M´enage Problem. The American Mathematical Monthly, August–September 1986, vol. 93, no. 7, s. 514–519. [3] Calda, E. Jeˇstˇe jednou o vˇeˇzov´ ych polynomech. Uˇcitel matematiky, 1998, roˇc. 6, ˇc. 3, s. 146–152. [4] Calda, E. Permutace s omezuj´ıc´ımi podm´ınkami a vˇeˇzov´e polynomy. Uˇcitel matematiky, 1998, roˇc. 6, ˇc. 2, s. 75–88. [5] Calda, E. Kombinatorika pro uˇcitelsk´e studium. 1. vyd´an´ı. Praha: Matfyzpress, 1996. ISBN 80-85863-13-8. [6] Cole, F. N. Kirkman Parades. Bulletin of the American Mathematical Society, 1922, vol. 28, s. 435–437. [7] Davis, E. W. A Geometric Picture of the Fifteen School Girl Problem. The Annals of Mathematics, 1897, vol. 11, s. 156–157. ¨ rrie, H. 100 Great Problems of Elementary Mathematics: Their History [8] Do and Solution. New York: Dover Publications, 1965. ISBN 0486613488. [9] Falcone, G. – Pavone, M. Kirkman’s Tetrahedron and the Fifteen Schoolgirl Problem. American Mathematical Monthly, 2011, vol. 118, s. 887–900. [10] Frame, J. S. – Stewart, B. M. Solution to Advanced Problem 3918. The American Mathematical Monthly, March 1941, vol. 48, no. 3, s. 216–219. [11] Graham, R. L. – Knuth, D. E. – Patashnik, O. Concrete Mathematics: A Foundation for Computer Science. 1st edition. Massachusetts: Addison Wesley, 1988. ISBN 0-201-14236-8. Chapter 1, Recurrent Problems, s. 1–20. ¨r, C. The Mathematics of Survival: From Antiquity to the Play[12] Groe ground. The American Mathematical Monthly, November 2003, vol. 110, no. 9, s. 812–825. [13] Hardy, G. H. – Wright, E. M. An Introduction to the Theory of Numbers. 4th edition. Oxford University Press, 1975. [14] Holst, L. On the ’probl`eme des m´enages’ from a probabilistic viewpoint. Statistic & Probability Letters, March 1991, vol. 11, no. 3, s. 225–231. ˇlka, M. – Sna ´ˇ [15] Kude sel, V. Josephova funkce. Rozhledy mat. – fyz., 1999, roˇc. 76, s. 217–221. ˇil, J. Kapitoly z diskr´etn´ı matematiky. 3. vyd´an´ı. [16] Matouˇ sek, J. – Neˇ setr Praha: Karolinum, 2007. ISBN 978-80-246-1411-3. 59

[17] Pegg, E. Social Golfer Problem. Math Games [online], August 2007. [Citov´ano 26. bˇrezna 2012]. Dostupn´e z: http://www.maa.org/editorial/mathgames/ mathgames_08_14_07.html#g15o3d7 ´ nek, R. Hanojsk´e vˇeˇze: Interdisciplin´arn´ı h´adanka. Vesm´ır, z´aˇr´ı 2010, [18] Pela roˇc. 89, s. 544–546. [19] Perelman, J. I. Zaj´ımav´a matematika. 2. vyd´an´ı. Praha: Mlad´a fronta, 1961. [20] Poole, D. G. The Towers and Triangles of Professor Claus (or, Pascal Knows Hanoi). Mathematics Magazine, December 1994, vol. 67, no. 5, s. 323–344. [21] Renault, M. Lost (and Found) in Translation: Andr´e’s Actual Method and Its Application to the Generalized Ballot Problem. American Mathematical Monthly, 2008, vol. 115, s. 358–363. [22] Renault, M. Four Proofs of the Ballot Theorem. Mathematics Magazine, 2007, vol. 80, no. 5, s. 345–352. [23] Ruskey, F. – Williams, A. The Feline Josephus Problem. 2010. [Citov´ano 27. ˇr´ıjna 2011]. Dostupn´e z: http://webhome.cs.uvic.ca/~ruskey/Publications/Josephus/ FelineJosephus.html [24] Schumer, P. The Josephus Problem: Once More Around. Mathematics Magazine, February 2002, vol. 75, no. 1, s. 12–17. [25] Shams-Baragh, A. Formulating The Extended Josephus Problem. 2002. [Citov´ano 20. srpna 2011]. Dostupn´e z: http://www.cs.manchester.ac.uk/~shamsbaa/Josephus.pdf [26] Shevelev, V. The M´enage Problem with a Known Mathematician. 2011. [Citov´ano 6. dubna 2012.] Dostupn´e z: http://arxiv.org/pdf/1101.5321v1.pdf [27] Stanley, R. P. Catalan Addendum [online]. Last version 22nd of October 2011 [citov´ano 19. bˇrezna 2012]. Dostupn´e z: http://www-math.mit.edu/~rstan/ec/ ´ , D. Z´aklady algebry. 1. vyd´an´ı. Praha: Matfyzpress, 2010. ISBN [28] Stanovsky 978-80-7378-105-7. [29] Stockmeyer, P. K. Variations on the Four-Post Tower of Hanoi Puzzle. Congressus Numerantium, 1994, vol. 102, s. 3–12. [30] Maximum Socializing on the Golf Course. Google Groups: sci.op-research [online]. [Citov´ano 26. bˇrezna 2012]. Dostupn´e z: http://groups.google.com/group/sci.op-research/browse_thread/ thread/2ca0d1b186314c40/ 60

[31] Tower of Hanoi. Wikipedia, The Free Encyklopedia [online]. Last revision 25th of August 2011 [citov´ano 6. z´aˇr´ı 2011]. Dostupn´e z: http://en.wikipedia.org/wiki/Tower_of_Hanoi ˇ ˇ e republiky [online]. [Citov´ano 27. [32] Webov´y port´al Sachov´ eho svazu Cesk´ bˇrezna 2012]. Dostupn´e z: http://www.chess.cz/www/informace/komise/kr/materialy/ schurigovy-tabulky.html

61