Kombinatorika rndr. Anton´ın Slav´ık, Ph. D
Download 376.07 Kb. Pdf ko'rish
|
|
a n je minimální počet kroků potřebný k přenesení n kotoučů z jednoho kolíku na jiný; zřejmě platí a 1 = 1, a 2 = 3. Ukážeme, že pro každé n ≥ 2 je splněna rekurentní rovnice a n = 2
a n −1 + 1. K tomu, abychom se dostali k největšímu kotouči a mohli jej přenést z levého kolíku na pravý, musíme nejprve přemístit zbývajících n − 1 kotoučů na prostřední kolík (k tomu je potřeba a n −1 kroků). Poté přeneseme největší kotouč z levého kolíku na pravý (1 krok) a zbývá přemístit n −1 kotoučů z prostředního kolíku na pravý (opět a n −1 kroků); platí tedy a n
a n −1 + 1 + a n −1 = 2
a n −1 + 1. Pomocí této rekurentní rovnice snadno spočteme, že a 8
5.2 Poznámka. Spočteme-li hodnoty a n pro malá přirozená čísla n, snadno uhodneme, že platí obecný vzorec a
= 2 n − 1; dokažte jej indukcí! 5.3 Cvičení. Uvažujme následující variantu hlavolamu „Hanojské věže : Jsou dány 3 kolíky; na prvním z nich je postavena věž z n kotoučů seřazených podle velikostí (největší je vespod), ostatní jsou prázdné. V každém kroku lze přenést jeden kotouč mezi prvním a druhým kolíkem, nebo mezi druhým a třetím kolíkem, a to tak, že větší kotouč nikdy nesmí ležet na menším. Jaký je nejmenší počet kroků potřebný k přenesení věže z prvního na třetí kolík? 5.4 Příklad. n zajatcům čekajícím na popravu bylo nařízeno, aby se rozestavili do kruhu. Postupně bude popravován každý druhý zajatec tak dlouho, dokud nezůstane naživu jen jeden z nich; tomu bude udělena milost. (Např. pro n = 4 bude postupně popraven druhý, čtvrtý a třetí zajatec, první přežije). Zjistěte, který zajatec zůstane naživu. Řešení. Nechť a n je číslo zajatce, který zůstane naživu (předpokládáme, že zajatci jsou očíslováni čísly 1 , . . . , n v tom pořadí, ve kterém stojí v kruhu vedle sebe). Zřejmě platí a 1 = a 2 = 1. Pro
a n , kde n ≥ 3, odvodíme rekurentní rovnici. Je-li n = 2k sudé, pak po provedení k poprav zbývá k zajatců s čísly 1 , 3, . . . , 2k − 1. Naživu zůstane a k -tý z nich; jeho číslo je 2 a k − 1. Platí tedy a 2 k = 2 a k − 1. Je-li
n = 2k + 1 liché, pak po provedení k + 1 poprav zbývá k zajatců s čísly 3, . . . , 2k − 1, 2k + 1. Naživu zůstane a
-tý z nich; jeho číslo je 2 a k + 1. Platí tedy a 2 k+1 = 2
a k + 1 . Pomocí těchto rekurentních rovnic lze spočítat a n
n. 5.5 Poznámka. Sestavíme-li si tabulku hodnot a n
n, můžeme uhodnout, že pro n = 2 k je a n = 1 a s každým zvýšením n o 1 roste a n o 2 tak dlouho, dokud nenarazíme na další mocninu dvojky. Formálně zapsáno: Je-li n = 2
k + l, kde l ∈ {0, . . . , 2 k − 1}, pak a n = 2
l + 1. Dokažte to matematickou indukcí! (Použijte obě nalezené rekurentní rovnice.) 5.6 Cvičení. [AIME 1996] Ve školní šatně je v řadě vedle sebe celkem 1024 uzavřených skříněk očíslo- vaných 1
, 2, . . . , 1024. Nudící se student prochází kolem skříněk zleva doprava, otevře první a následně každou druhou skříňku (tj. skříňky 1 , 3, . . . , 1023). Poté se vrací zpět zprava doleva, všímá si pouze zbý- vajících uzavřených skříněk, a opět otvírá první a pak každou druhou (tj. skříňky 1024 , 1020, . . .). Takto postupuje do té doby, než otevře všechny skříňky. Zjistěte, jaké číslo měla poslední otevřená skříňka. 5.7 Příklad. [MO Česká republika 1997/98] V jistém jazyce jsou pouze dvě písmena, A a B. Pro slova tohoto jazyka platí: 1) Jediné slovo délky 1 je A. 10
2) Libovolná skupina písmen X 1 X 2 . . . X n X n+1 , kde X i ∈ {A, B} pro každý index i, tvoří slovo délky n + 1, právě když obsahuje aspoň jedno písmeno A a přitom není tvaru X 1 X
. . . X n A, kde X 1 X 2 . . . X n je slovo délky n. Najděte a) všechna slova délky 4, b) vzorec pro počet p n
n. Řešení. a) K nalezení slov délky 4 potřebujeme znát slova délek 3 a 2. Slova délky 2 jsou AB, BA, slova délky 3 jsou AAA, AAB, ABB, BAB, BBA, slova délky 4 jsou AAAB, AABB, ABAA, ABAB, ABBB, BAAA, BAAB, BABB, BBAB, BBBA. b) Už víme, že p 1 = 1, p 2 = 2, p 3 = 5, p 4 = 10. Z pravidel pro tvoření slov snadno zjistíme, že počet slov délky
n + 1 končících na A je 2 n − p n a počet slov délky n + 1 končících na B je 2 n − 1. Úloha tedy vede na rekurentní rovnici p n+1 = (2 n − p n ) + (2
n − 1) = 2
n+1 − 1 − p
n . Použijeme-li tuto rovnici dvakrát po sobě, dostaneme p n+2
= 2 n+2
− 1 − p n+1
= 2 n+2
− 1 − (2 n+1
− 1 − p n ) = p n + 2 n+1 . Počet slov délky n, kde n = 2k je sudé číslo, je roven p 2 k = 2
2 k −1 + 2 2 k −3 + · · · + 2 3 + p 2 = 2
· 4 k − 1 3 . Počet slov délky n, kde n = 2k − 1 je liché číslo, je roven p 2 k −1 = 2 2 k −2 + 2 2 k −4 + · · · + 2 2 + p 1 = 4 k − 1
3 . 5.8 Cvičení. [MO Česká republika 1997/98] V jistém jazyce jsou pouze dvě písmena, A a B. Přípustná jsou v něm pouze taková slova, v nichž nestojí vedle sebe více než dva stejné znaky. Dokažte, že pro počet p
všech přípustných slov délky n platí p 1 = 2,
p 2 = 4 a p k+2
= p k+1 + p k pro každé přirozené číslo
k. 5.9 Příklad. [MO Česká republika 2003/04] Pro libovolné přirozené číslo n sestavme z písmen A a B všechna možná „slova délky n a označme p n počet těch z nich, která neobsahují ani čtveřici AAAA po sobě jdoucích písmen A, ani trojici BBB po sobě jdoucích písmen B. Určete hodnotu výrazu p 2004 − p 2002
− p 1999
p 2001
+ p 2000 . Řešení. Počet vyhovujících slov délky n, která končí písmenem A, resp. B, označme a n , resp. b n . Platí p n = a n + b n . Nechť n = 4. Vyhovující slovo končící písmenem A má jednu z koncovek BA, BAA, nebo BAAA. Počet slov prvního typu je b n −1
b n −2 , třetího typu b n −3 . Proto
a n = b n −1 + b n −2 + b n −3 . Podobně pro n = 3 má vyhovující slovo končící písmenem B jednu z koncovek AB, ABB, tudíž b n
a n −1 + a n −2 . Z předchozích dvou vztahů pro každé n ≥ 6 plyne a n
b n −1 + b n −2 + b n −3 = ( a n −2 + a n −3 ) + (
a n −3 + a n −4 ) + (
a n −4 + a n −5 ) =
= a n −2 + 2
a n −3 + 2 a n −4 + a n −5 a podobně b n = a n −1 + a n −2 = (
b n −2 + b n −3 + b n −4 ) + ( b n −3 + b n −4 + b n −5 ) = = b n −2 + 2
b n −3 + 2 b n −4 + b n −5 . 11 Sečtením posledních dvou rovností dostaneme p n = a n + b n = p n −2 + 2
p n −3 + 2 p n −4 + p n −5 . Proto pro libovolné n ≥ 6 (a speciálně pro n = 2004) platí p n − p n −2 − p n −5 p n −3 + p n −4 = 2 . 5.10 Cvičení. [MO Česká republika 2003/04] Pro libovolné přirozené číslo n sestavme z písmen A a B všechna možná „slova délky n a označme p n počet těch z nich, která neobsahují ani trojici AAA po sobě jdoucích písmen A, ani dvojici BB po sobě jdoucích písmen B. Určete, pro která přirozená čísla n platí, že obě čísla p n
p n+1
jsou sudá. 6. Úlohy o obarvení a pokrytí 6.1 Příklad. Každý bod v rovině je buď červený, nebo modrý. Dokažte, že pro aspoň jednu z těchto barev platí, že pro každé d > 0 existují dva body dané barvy, jejichž vzdálenost je d. Řešení. Předpokládejme, že tvrzení neplatí. Pak existují kladná čísla a, b taková, že žádné dva červené body nemají vzdálenost a a žádné dva modré body nemají vzdálenost b. Bez újmy na obecnosti před- pokládejme, že a ≤ b (jinak stačí zaměnit červenou a modrou barvu). Vezměme libovolný modrý bod C a sestrojme trojúhelník ABC tak, že |AC| = |BC| = b a |AB| = a. Body A, B nemohou být modré (jejich vzdálenost od modrého bodu je b), takže jsou červené; to je spor s tím, že žádné dva červené body nemají vzdálenost a. 6.2 Cvičení. Každý bod v rovině je obarven jednou ze tří barev. Dokažte, že existují dva stejně obarvené body o vzdálenosti 1. 6.3 Příklad. Každý bod v rovině je buď červený, nebo modrý. Dokažte, že existuje obdélník, jehož vrcholy jsou téže barvy. Řešení. Uvažujme pouze body se souřadnicemi ( x, y), kde x ∈ {1, 2, 3} a y ∈ {1, . . . , 9}. Počet možností, jak obarvit jeden řádek tvořený třemi body je 8. Protože řádků je 9, existují mezi nimi dva stejně obarvené; předpokládejme, že jde o k-tý a m-tý řádek. Pro každé x ∈ {1, 2, 3} mají body (x, k) a (x, m) stejnou barvu. Protože jde o tři dvojice, existují dvě dvojice stejné barvy a nalezené čtyři vrcholy tvoří hledaný obdélník. 6.4 Cvičení. Každý bod v rovině je obarven jednou z n barev. Dokažte, že existuje obdélník, jehož vrcholy jsou téže barvy. 6.5 Cvičení. Každý bod v rovině je buď červený, nebo modrý. Dokažte, že existuje rovnostranný trojú- helník, jehož vrcholy jsou téže barvy. 6.6 Cvičení. [MO Česká republika 1994/95] Každý bod obvodu čtverce o straně 10 cm je obarven jednou ze dvou barev. Dokažte, že při libovolném obarvení můžeme na obvodu čtverce vždy najít tři body stejné barvy tak, aby trojúhelník s těmito vrcholy měl obsah aspoň 25 cm 2 .
n − 1) × (n − 1) jednotkových čtverečků. Kolika způsoby lze obarvit vrcholy těchto čtverečků (tj. celkem n 2 vrcholů) červenou a modrou barvou tak, aby každý jednotkový čtvereček měl dva vrcholy červené a dva modré? Řešení. Vrcholy ve spodním řádku můžeme obarvit libovolně. Rozlišíme dva případy: a) Barvy vrcholů ve spodním řádku se střídají; existují právě dvě obarvení spodního řádku, která mají tuto vlastnost. Snadno si rozmyslíme, že to znamená, že i barvy ve všech dalších řádcích se musejí střídat a v každém řádku můžeme libovolně zvolit jedno ze dvou „střídavých obarvení. Existuje tedy celkem 2 n
b) Ve spodním řádku existují dva sousední vrcholy stejné barvy; existuje celkem 2 n −2 obarvení spodního řádku, které mají tuto vlastnost. Pak existuje pouze jedno přípustné obarvení všech zbývajících vrcholů. Celkový počet všech přípustných obarvení je tedy 2 n+1 − 2.
12 6.8 Příklad. [MO Česká republika 1996/97] Každá z úhlopříček pravidelného n-úhelníku (n ≥ 5) je obarvena modře nebo červeně. Je povoleno postupně přebarvovat úhlopříčky tak, že v každém kroku vybereme jeden vrchol a změníme barvy všech úhlopříček, které z něj vycházejí (z modré na červenou a naopak). Rozhodněte, zda lze vždy úhlopříčky přebarvit tak, aby existovala a) lomená čára b) uzavřená lomená čára složená vesměs z modrých úhlopříček a procházející každým vrcholem n-úhelníku právě jednou. Řešení. a) Odpověď je ano. Nechť A 1 , . . . , A n jsou (v tomto pořadí) vrcholy n-úhelníku. Položme X 1 X 2 . . . X n = A 1 A 3 A 5 . . . A n −1 A 2 A 4 . . . A n je-li n sudé, X 1 X 2 . . . X n = A 1 A 3 A 5 . . . A n A 2 A 4 . . . A n −1 je-li n liché. Ukážeme, že úhlopříčky lze přebarvit tak, že všechny úsečky lomené čáry X 1
2 . . . X
n jsou modré. K tomu stačít volit za i postupně hodnoty 1, . . . , n − 1 a pokaždé zkontrolovat, zda je úsečka X i X i+1 modrá.
Pokud ne, přebarvíme všechny úhlopříčky vycházející z vrcholu X i+1 . Zřejmě platí, že po provedení i-tého kroku je úsek X 1 X
. . . X i X i+1 celý modrý. b) Odpověď je ne. Jednoduchý protipříklad představuje pětiúhelník se všemi úhlopříčkami obarvenými červeně. Z každého vrcholu vycházejí 2 úhlopříčky, při každém přebarvení se tedy počet modrých úh- lopříček změní o sudé číslo. Nelze proto dosáhnout toho, aby všech pět úseček nějaké uzavřené lomené čáry bylo modrých. 6.9 Cvičení. [MO Česká republika 1996/97] Nechť M je množina úhlopříček pravidelného n-úhelníku, která neobsahuje žádnou uzavřenou lomenou čáru. Ukažte, že každé výchozí obarvení úhlopříček lze podle pravidel předchozí úlohy tak, že všechny úhlopříčky z M budou modré. (Využijte toho, že pokud M neobsahuje uzavřenou lomenou čáru, pak existuje vrchol n-úhelníku náležející právě jedné úhlopříčce z M .)
6.10 Cvičení. [MO Česká republika 1996/97] V rovině je dáno n bodů, některé jsou pospojovány úsečkami tak, že z každého bodu vycházejí právě 3 úsečky. Dokažte, že tyto body lze obarvit modrou a červenou barvou tak, že žádný bod nemá dva sousedy stejné barvy, jakou má on sám. 6.11 Cvičení. [Austrian-Polish Mathematics Competition 2000] Pro která přirozená čísla n ≥ 5 platí, že vrcholy pravidelného n-úhelníka lze obarvit nejvýše šesti barvami tak, že každých pět po sobě jdoucích vrcholů má různé barvy? 6.12 Příklad. [MO Česká republika 1995/96] Je dáno šest tříprvkových podmnožin konečné množiny X. Dokažte, že prvky množiny X je možné obarvit dvěma barvami tak, aby žádná ze šesti daných podmnožin nebyla jednobarevná, tj. neměla všechny tři prvky stejné barvy. Řešení. Označme dané podmnožiny A 1 , . . . , A 6 . Tvrzení dokážeme indukcí podle počtu n prvků množiny X. Začneme s případem n = 6. (Pokud má množina X méně než 6 prvků, doplníme ji na šestiprvkovou přidáním nových prvků; množiny A i se tím nezmění.) Protože 6 3 = 20 > 2
· 6, existuje tříprvková množina
Y ⊂ X, která se nerovná ani žádné z množin A i , ani žádnému doplňku X − A
i . Obarvíme-li prvky Y jednou barvou a prvky X − Y barvou druhou, dostaneme přípustné obarvení. Nyní předpokládejme, že množina X má n ≥ 7 prvků. Pak existuje dvojice různých prvků u, v ∈ X, které spolu neleží v žádné z množin A i . (Opravdu, existuje totiž nejvýše 6 · 3 2 = 18 dvojic prvků, které patří do některé z množin A i , zatímco všech dvojic prvků z X je
7 2 = 21.) Tuto dvojici prvků u, v „slepíme
do jednoho nového prvku w, tj. kdykoliv nějaká množina A i obsahuje
u nebo v, nahradíme jej prvkem w. Máme tak šest tříprvkových podmnožin n − 1 prvkové množiny X = (X − {u, v}) ∪ {w}, a podle indukčního předpokladu existuje přípustné obarvení prvků X . Pak stačí vrátit se k původním množinám X, A
1 , . . . , A 6 a použít nalezené obarvení, přičemž prvky u, v budou mít barvu prvku w. 6.13 Příklad. Dokažte, že čtverec o rozměrech 10 × 10 nelze beze zbytku pokrýt 25 dlaždicemi násle- dujícího tvaru: Řešení. Předpokládejme, že existuje nějaké pokrytí. Obarvíme políčka dlaždic střídavě černou a bílou 13
barvou (tak, jako na šachovnici). Dostaneme tak dva druhy dlaždic, s jedním černým políčkem a třemi bílými, nebo obráceně: Protože celkový počet černých políček je roven celkovému počtu bílých políček, musíme mít od každého ze dvou druhů stejný počet dlaždic. Ale počet dlaždic je 100 /4 = 25 (liché číslo), což je spor. 6.14 Příklad. Dokažte, že čtverec o rozměrech 10 × 10 nelze beze zbytku pokrýt obdélníkovými dlaždi- cemi o rozměrech 4 × 1. Řešení. Očíslujme políčka čtverce podle následujícího obrázku: 0 1 2 3 0 1 2 3 0 1 0 1 2 3 0 1 2 3 0 1 0 1 2 3 0 1 2 3 0 1 0 1 2 3 0 1 2 3 0 1 0 1 2 3 0 1 2 3 0 1 0 1 2 3 0 1 2 3 0 1 0 1 2 3 0 1 2 3 0 1 0 1 2 3 0 1 2 3 0 1 0 1 2 3 0 1 2 3 0 1 0 1 2 3 0 1 2 3 0 1 Předpokládejme nyní, že existuje nějaké pokrytí čtverce, a umístěme nejprve všechny vodorovné dlaždice. Každá zakryje čtyři různé cifry; nezakryto zůstane n+10 nul, n+10 jedniček, n dvojek, n trojek (kde n je nějaké číslo). Každá svislá dlaždice zakryje 4 stejné cifry; to znamená, že n i n + 10 jsou čísla dělitelná čtyřmi, ale to se pro žádné n nemůže stát. 6.15 Příklad. [MO Korea 2000] Chceme vydláždit obdélník o rozměrech m × n, kde m, n jsou přirozená čísla větší než 1. K dispozici máme následující dva druhy dlaždic (každá je složena ze čtyř jednotkových čtverečků): Dokažte, že obdélník je možno beze zbytku vydláždit právě tehdy, když součin mn je dělitelný osmi. Řešení. Nechť mn je dělitelné osmi. Důkaz, že obdélník lze beze zbytku vydláždit, rozdělíme na dva případy: a) m i n jsou sudá. Bez újmy na obecnosti předpokládejme, že 4 |m a 2|n. Vezmeme-li dvě dlaždice Download 376.07 Kb. Do'stlaringiz bilan baham: 
|