Riešenie príkladov z Dirichletovho princípu

Dirichletov princíp (DP)

1. Možných súčtov je 11 (od 2 po 12), preto treba hodiť aspoň 12-krát.

2. Možných súčtov je 16 (od 3 po 18), preto treba hodiť aspoň (3.16 + 1) = 49-

krát.

3.

a) Rozlíšené kocky : rôznych dvojíc je 6.6 = 36, treba aspoň 2.36 + 1 = 73

hodov.

b) Nerozlíšené kocky : rôznych dvojíc je 21, treba aspoň 2.21+1 = 43 hodov.

4.

a) Sporom. Ak sú všetky menšie ako

b

n , súčet je menší ako n.

b

n = b. Spor.

bcd) Až na ostré/neostré/obrátené nerovnosti to isté ako a).

5. Z Eulerovej vety ⇒, že mnohosten má 21 hrán, teda súčet stupňov vrcholov

je 42. Keďže 42 ≥ 37 = 9.4 + 1, z DP ⇒, že z niektorého vrcholu vychádza
aspoň 5 hrán, q.e.d.

6. Hrán je 11, súčet počtov hrán v stenách 22, stien 7, z DP ⇒, že ∃ stena s

aspoň 4 hranami, ale keďže každá stena má aspoň 3 hrany, majú steny dokopy
aspoň 21 hrán, preto jediná možnosť je, že jedna stena má 4 hrany a všetky
ostatné po 3 hrany.

7. Záhradu 80×90 rozdeľme na 10×18 obdĺžnikov tvaru 8×5. Máme 365 stromov

v 180 obdĺžnikoch, z DP ⇒, že v niektorom sú aspoň 3.

8. Obdĺžnik 27 × 36 rozdeľme na 9 × 18 obdĺžnikov tvaru 3 × 2 a každý z nich

uhlopriečkou na dva trojuholníky s plochou 3. Máme 1945 bodov v 9.18.2 =
324 trojuholníkoch, z DP ⇒ q.e.d.

9. 13 vysielačov pokryje max. plochu 13.π.802 = 83200.π < 268138 km

2.

10.

11.

12.

13. Štvorec rozrežeme na 25 štvorčekov so stranou

1
5 . Z DP v niektorom ležia

aspoň 3 z 51 bodov. Keďže

√

2

2 ·

1
5 =

√

2

10 <

1
7 , celý tento štvorec leží v kruhu so

stredom v jeho priesečníku uhlopriečok a polomerom

1
7 . V tomto kruhu ležia

teda aspoň 3 body, q.e.d.

14. Označme naše čísla c1, . . . , c82. Ak niektoré z čísel c1 − c2, c1 − c3, . . . , c1 − c82

dáva po del. 81 zvyšok 0, vyhrali sme. Ak nie, máme 81 čísel, ktoré dávajú
nanajvýš 80 zvyškov, podľa DP niektoré dve dávajú rovnaký zvyšok. BUNV
nech sú to c1 − ci = 81a + z, c1 − cj = 81b + z, pričom i 6= j a 0 ≤ z < 81.
Potom ale ci − cj = (c1 − cj) − (c1 − ci) = (81b + z) − (81a + z) = 81(b − a).

15. Dokážeme tvrdenie, z ktorého budú vyplývať tvrdenia 16 a 17. Ku každému

n nesúdeliteľnému s 10 existuje číslo tvaru 111. . . 1, ktoré je ním deliteľné.
Dôkaz: Zoberme čísla 1, 11, . . . , 11...1, z ktorých posledné má n+1 cifier. Z DP
niektoré dve dávajú rovnaký zvyšok po delení n. Preto ich rozdiel je deliteľný
n. (Tým je dokázané tvrdenie 16, lebo ich rozdiel je tvaru 11 . . . 100 . . . 0.)
Pre n nesúdeliteľné s 10 z toho dostávame, že keďže n delí 11 . . . 100 . . . 0 =
11 . . . 1.10k, delí aj 11 . . . 1.

16. Keďže prvočísla rôzne od 2 a 5 sú nesúdeliteľné s 10, môžme použiť predchá-

dzajúcu vetu.

1

17. Označme čísla a1, . . . , an. Ďalej označme bi = a1 +. . .+ai. Ak niektoré bi dáva

zvyšok 0 po delení n, hotovo, inak máme n čísel, ktoré dávajú najvac n − 1
zvyškov. Z DP niektoré 2 dávajú rovnaký zvyšok, preto ich rozdiel bj − bi je
deliteľný n. Ich rozdiel ale je ai+1 + . . . + aj.

18.

19. Vyplýva z úlohy 20.

20. Zoberme čísla p, p2, . . . , p10

n+1 +1. Niektoré dve z nich podľa DP dávajú rov-

naký zvyšok po delení 10n+1. Nech sú to pk a pl. Potom 10n+1|pl − pk =
pk(pl−k − 1). Keďže 10 je nesúdeliteľné s p, ⇒ z toho, že 10n+1|pl−k − 1,
čiže pl−k ≡ 1(mod 10n+1). To ale znamená, že pl−k končí skupinou n núl a
jednotkou.

21. Sporom. Keby boli najviac 2 ofic. jazyky, tak oficiálnymi jazykmi hovorí do-

kopy najviac 30 delegátov. Každým z ostatných 9 jazykov hovoria najviac 4
delegáti. To ale znamená, že delegátov je najviac 66 – spor.

22.

23.

24.

25.

26.

27.

28.

29.

30.

31.

32.

33.

34.

35.

Spočítateľné množiny

1.

2.

3.

4.

5.

6.

7.

2

8.

9.

10.

11. Intervalu (a, b) priraďme dvojicu a, b ∈ Q × Q. Zjavne je to injekcia, preto má

množina vš. intervalov s rac. koncami mohutnosť nanajvýš rovnú mohutnosti
množiny Q × Q, tá je ale spočítateľná.

12. Napr. X = Qn. Rac. čísla sú hustá podmnožina R, teda pre ľubovoľné ∀ r, ε ∈

R ∃ q ∈ Q; |r − q| < ε. Preto keď máme a = (a1, . . . , an), stačí nájsť
x1, . . . , xn ∈ Q; |ai − xi| <

ε

n . Také xi určite existujú a zároveň je potom

P |xi − ai| < n.

ε

n = ε, takže X = Q

n naozaj vyhovuje.

13. V každom z nich leží aspoň jedno rac. číslo. Každému intervalu priraďme

niektoré rac. číslo z neho. Keďže sú disjunktné, je to injekcia, teda mohutnosť
množiny intervalov je nanajvýš rovná mohutnosti Q, teda množina intervalov
je spočítateľná.

14.

a) Z analýzy vieme, že pre rastúcu funkciu je limx→a+ f (x) = supx<af (x).

b) . . . nejako cez disjunktné intervaly na osi y.

15. bolo na cvikách

16. Zjavne Tk(0) = {(0, 0, . . . , 0, . . .)}, preto |Tk(0)| = 1.

Keď X obsahuje aspoň 2 prvky (BUNV 1 a 2), môžme prirodzenému číslu n
priradiť postupnosť n jednotiek a dvojky, preto je určite |X| ℵ0. Špeciálne
|Tk(0, 1)| ℵ0, |Tk(N )| ℵ0 a |Tk(Q)| ℵ0.

Zobrazme každú postupnosť z Tk(X) na konečnú postupnosť, ktorú z nej do-
staneme, keď z konca vynecháme všetky rovnaké členy okrem jedného. (T.j.
napr. postupnosť 3, 1, 4, 1, 5, 2, 2, . . . , 2, . . . na 3, 1, 4, 1, 5, 2.) Toto je zjavne in-
jekcia, preto mohutnosť Tk(X) je nanajvýš rovná mohutnosti množiny všet-
kých konečných postupností prvkov X.

Množina všetkých konečných postupností 0 a 1 má mohutnosť ℵ0, lebo každá
z nich zodpovedá nejakému konečnému desatinnému rozvoju reálneho (a teda
zároveň racionálneho) čísla. (Teda napr. postupnosti 0,1,0,1,1,1 priradíme číslo
0, 0101111 – tú jednotku na konci musíme ku každému pridať kvôli postup-
nostiam, ktoré končia 0.) Množinu kon. postupností prir. čísel zobrazíme do
množiny kon. postupností 0 a 1 tak, že číslo n zakódujeme postupnosťou n
núl a jednotkou. Množinu kon. postupností rac. čísel zobrazíme do postupnosti
prir. čísel tak, že číslu

p
q ; p ∈ Z, q ∈ N, (p, q) = 1 priradíme 1, p, q ak p ≥ 0

a 2, −p, q ak p < 0. Preto aj množina všetkých kon. postupostí prirodzených,
resp. racionálnych čísel má mohutnosť ℵ0.

Teda je |Tk(0, 1)| ℵ0, |Tk(N )| ℵ0, |Tk(Q)| ℵ0, a teda podľa C-B vety
|Tk(0, 1)| = |Tk(N )| = |Tk(Q)| = ℵ0.

Zjavne každému reálnemu číslu môžme priradiť nekonečnú postupnosť zlo-
ženú zo samých takých čísel, preto |Tk(R)| c. Keby sme dokázali, že mo-
hutnosť množiny všetkých konečných postupností reálnych čísel je c, boli by
sme hotoví. Keďže sa mi to už nechce rozpisovať, využijem bez dôkazu, že
|Rn| = |R| = | (0, 1) |. Každej konečnej postupnosti a1, . . . , an reálnych čísel
viem podľa práve uvedenej vety priradiť číslo x ∈ (0, 1). Keď jej priradím číslo
n + x, dostanem takto injekciu z množiny všetkých kon. postupností reálnych
čísel do R, takže naozaj |Tk(R)| = c.

3

17. Keďže P je spoč. množina, môžme jej prvky označiť P = {p1, p2, . . .}. Keď

bude druhý hráč ťahať tak, že v n-tom ťahu dá číslicu, ktorú pn nemá na 2n-
tom mieste, výsledná postupnosť nemôže patriť do P . (Dôkaz ako pri Canto-
rovej diagonálnej metóde - keď tam patrí, nech je to pk, ale od pk sa výsledná
postupnosť líši na 2k-tom mieste.)

18. Pre P = 0, 1

N nech druhý hráč ťahá ako chce, výsledok bude patriť do P .

Preto druhý hráč nemá vyhrávajúcu stratégiu, čiže P nie je spočítateľná.

19. Čo je podgrupa ?

Príklady rôznych typov

1.

2.

3. Určite vieme vybrať k + 1 čísel – napr. všetky nepárne. Stačí dokázať, že

nevieme viac. Indukciou.

1◦ Z 1 čísla vieme vybrať najviac 1.

2◦ Majme 2k + 1 čísel. Ak vyberieme číslo 2k + 1, zo zvyšných žiadna dvo-

jica nesmie mať súčet 2k + 1, preto z každej z dvojíc [1, 2k], [2, 2k −
1], . . . , [k, k + 1] môžme vybrať najviac jedno číslo, dokopy najviac k + 1
čísel.

Ak číslo 2k + 1 nevyberieme: Ak vyberieme 2k, tak už z každej z dvojíc
[1, 2k − 1], . . . , [k − 1, k + 1] môžme vybrať najviac jedno a navyše môžme
ešte vybrať k. Takže vyberieme najviac 1 + (k − 1) + 1 = k + 1 čísel. Ak
nevyberieme ani 2k, vyberáme vlastne už len z 2k − 1 čísel, z nich podľa
ind. predp. vieme vybrať najviac k čísel.

Preto môžme vybrať najviac k + 1 čísel.

4. Každý súčet je z množiny {−n, . . . , −1, 0, 1, . . . , n}. Tá má 2n + 1 prvkov,

riadkov, stĺpcov a diagonál je však dokopy 2n+2, preto taká matica neexistuje.

5. Každý má medzi 0 a n−1 známymi. Ak žiadni dvaja nemajú rovnako, znamená

to, že jeden má 0 známych, atď., až jeden má n − 1 známych. Potom ale ten,
čo pozná všetkých, sa pozná aj s tým, ktorý nepozná nikoho, spor.

6.

7.

8.

9.

10. Možné výsledky sú (v tvare [jednotky, dvojky, trojky]) : [3, 0, 0], [0, 3, 0],

[0, 0, 3], [2, 1, 0], [2, 0, 1], [1, 2, 0], [1, 0, 2], [0, 2, 1], [0, 1, 2], [1, 1, 1]. Možných
výsledkov je teda 10, študentov 41 a z DP ⇒ dok. tvrdenie.

11. Predstavme si kompletný graf, ktorého vrcholy sú členovia komisie. Ofarbime

hranu medzi A a B, keď sú spolu na zasadnutí. Zo zadania vieme, že každú
hranu ofarbíme najviac raz. Pri jednom zasadaní však ofarbíme

10

2

= 45

4

hrán, zasadaní bolo 40, teda tento graf musí mať aspoň 1800 hrán. Kn má

n

2

hrán. Je teda

1800

≤

n

2

=

n.(n − 1)

2

=

1

2

n

2 −

1

2

n

n

2 − n − 3600 ≥ 0

Zjavne pre n ≤ 60 je n2 − n − 3600 < n2 − 3600 ≤ 602 − 3600 = 0, preto
n > 60.

12. Podobne. Vrcholy sú ľudia, keď vytvoríme komisiu, všetkých členov pospájame

hranami. Zo zadania ⇒, že žiadni dvaja ľudia nie sú spolu vo viac ako 1
komisii, preto každú hranu ofarbíme max. raz. Hrán je

25

2

= 300, 1 komisia

ofarbí 10 hrán, preto je komisii najviac 30.

13. To isté ako úloha 7, len v svetlomodrej.

14.

15.

16.

17. Teda toto bol buď blbý vtip, alebo som to zle pochopil.

18.

5