Kombinatorika rndr. Anton´ın Slav´ık, Ph. D


Download 376.07 Kb.
Pdf ko'rish
bet3/4
Sana19.12.2017
Hajmi376.07 Kb.
#22594
1   2   3   4

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

= 255.



5.2 Poznámka. Spočteme-li hodnoty

a

n



pro malá přirozená čísla

n, snadno uhodneme, že platí obecný

vzorec

a

n



= 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

k



-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

pro každé přirozené



n.

5.5 Poznámka. Sestavíme-li si tabulku hodnot

a

n

pro malá čísla



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

2



. . . 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

všech slov délky



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

n



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

, druhého typu



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

a



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

.

6.7 Příklad. [IMO Shortlist 1996] Uvažujme čtvercovou síť složenou z (



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

takovýchto obarvení.



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

X



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

2



. . . 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:
1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling