Skúšky

Diskrétna matematika – príklady zo skúšok v lete

c

MišoF.

1. Dokaz, ze plati:

(n + r − 1)!

r!

−

n

1

·

(n + r − 3)!

(r − 2)!

+

n(n − 1)

1.2

·

(n + r − 5)!

(r − 4)!

− · · · =

n!(n − 1)!

r!(n − r)!

Riešenie.
Predeľte obe strany (n − 1)!, napravo ostane

n

r

, čo sú všetky kombinácie r

prvkov z n. Naľavo ostane:

n + r − 1

r

−

n

1

·

n + r − 3

r − 2

+

n

2

·

n + r − 5

r − 4

− · · ·

Potrebujeme ukázať, že je to to isté. Spočítajme teda kombinácie r prvkov z n
pomocou inklúzie a exklúzie.

n+r−1

r

sú všetky kombinácie s opakovaním, od

nich potrebujeme odčítať tie, v ktorých sa niečo opakuje. Člen

n
k

· n+r−1−2k

r−2k

predstavuje kombinácie s opakovaním, v ktorých sa aspoň k prvkov opakuje –
vyberieme, ktorých k sa opakuje, každý z nich vezmeme dvakrát a zvyšných
r − 2k prvkov vyberieme ľubovoľne.

2. Nech A,B su dve konecne mnoziny, k ≥ 1 prirodzene cislo. Medzi A a B je ustanoveny mnoho-
znacny vztah, ze kazdemu prvku mnoziny A zodpoveda prave k prvkov mn. B a naopak kazdemu
prvku mn. B zodpoveda prave k prvkov mn. A. Dokaz, ze medzi A a B existuje bijekcia (kazdemu
prvku je potom priradeny prvok v sulade s mnohoznacnym vztahom).

3. Dokaz odhad poctu Spernerovych systemov An, pricom Tn =

n

bn/2c

:

2

Tn < A

n <

2Tn

Tn

Riešenie.
Prvá nerovnosť: Zoberme Spernerov systém, ktorý obsahuje práve všetky pod-
množiny {1, . . . , n}, ktoré majú práve bn/2c prvkov. Potom aj každá jeho pod-
množina je Spernerov systém, takýchto Spernerovych systémov je práve 2Tn ,
zjavne existujú aj iné Spernerove systémy, preto je nerovnosť ostrá.

4. Dokaz, ze v dvojfarebnom Kn, n ≥ 10 existuje aspon

n

2

2 −

19n

2 +61 jednofarebnych trojuholnikov.

5. Nech A,B su konecne mnoziny, |A| = n, |B| = m. Dokaz:

a) ak A a B su disjunktne, tak |A ∪ B| = n + m

b) |A × B| = nm

c) |AB] = nm

6. Nech f je zobrazenie z N × N do N take, ze ∀m, n ∈ N; f (n, 0) = n ∧ f (n, m + 1) = f (n, m) + 1.
Dokaz f (m, n) = m + n.

Na teorke daval klasiky – A(r), grafy, Ramseya, Halla, postupnosti, nepriatelov. . . Ak mal

niekto 4 priklady viac-menej dobre, dostal este jeden a ak to mal 100%-tne, po vacsine isiel za 2
do bace. Mat priklad z pisomky dobre znamenalo tam mat pekne vyzerajucu omacku a spravny
zaver, podrobnosti ho vobec nezaujimali.

1. S je mnozina disjunktnych intervalov (nie jednoprvkovych) na R. Dokazte, ze S je spocitatelna.

Riešenie.
V každom z intervalov leží nejaké racionálne číslo, tieto sú navzájom rôzne,
lebo intervaly sú disjunktné. Preto je intervalov najviac |Q|.

1

2. Pocet rozsadeni n nepriatelskych dvojic okolo okruhleho stola.

3. Mnozina A ⊆ N je zhora neohranicena, potom |A| = |N|.

4. Dokazte, ze system mnozin {S1, . . . , Sm} ma m roznych reprezentantov, ak kazda z mnozin ma
prave r prvkov a kazdy prvok sa nachadza prave v r mnozinach.

5. Dokazte, ze v dvojfarebnom K24 existuje aspon jeden jednofarebny K4.

6. Oznacme En = {(x1, . . . , xn) | xi ∈ {0, 1}}, pre x = (x1, . . . , xn), y = (y1, . . . , yn) definujme
x y ⇐⇒ ∀i; xi ≤ yi. Dokazte, ze (En, ) je ciastocne usporiadana mnozina. Aky je maximalny
pocet navzajom neporovnatelnych prvkov?

1. Mame n2 + 1 prvkovu postupnost roznych prirodzenych cisel. Ukazte, ze existuje jej monotonna
podpostupnost dlzky n + 1.

2. Mame dane j, k a c1, c2, . . . , ck. Kolko je vsetkych kombinacii s opakovanim j prvkov z k, ze
∀i; i-ty prvok sa opakuje najviac ci krat?

3. Priklad s hyperkockou. Prelozene: A je lubovolna mnozina n-prvkovych binarnych vektorov s k
jednotkami a B obsahuje vsetky take vektory, ktore dostaneme z niektoreho vektoru z A pridanim
jednotiek tak, aby jednotiek bolo l. Treba ukazat:

|A|

n
k

≤

|B|

n

l

Napr. ked n = 3, k = 1, l = 2, A = {(0, 0, 1), (1, 0, 0)} tak B = {(1, 0, 1), (1, 1, 0), (0, 1, 1)}.

4. Konigova veta (to s tou maticou jednotiek a nul)

5. Ak R(m, n − 1) = 2p, R(m − 1, n) = 2q (teda su parne), potom plati: R(m, n) < R(m, n − 1) +
R(m − 1, n).

6. Mnozina Q ∪ h0, 1i je spocitatelna. Dokazte. (Pozn. autora: Takto sa to zachovalo. Zjavne je to
blbosť, asi tam má byť prienik.)

Z prikladov na skuske dalej: Pocet rozsadeni manzelskych parov, Spernerova veta, Ramseyove

cisla, Hallovo kriterium, 2k + 1 papierikov kolko mozme vybrat tak aby ked vyberieme a,b,c tak
a + b sa nerovna c, dokazat inkluziu exkluziu, odvodit Eulerovu funkciu, odvodit A0(r).

1. Kolko je moznych rozsadeni n nepriatelskych dvojic okolo okruhleho stola s ocislovanymi sto-
lickami?

2. Mame postupnost n2 + 1 roznych prir. cisel. Dokazte, ze existuje rydzo monotonna podpostup-
nost dlzky n + 1.

3. Ostra nerovnost pri Ramseyho cislach, ak tie dve su parne. (Pozn. autora: viď vyššie)

4. Hallova veta.

5. ℵ0 × ℵ0 = ℵ0

6. Pocet particii cisla n na najviac m scitancov sa rovna poctu partici cisla m + n na m scitancov.

1. Dokazte, ze plati tato ohavna (na prve pohlady) suma, ci co:

(n + r − 1)!

r!

−

n

1

·

(n + r − 3)!

(r − 2)!

+

n(n − 1)

1.2

·

(n + r − 5)!

(r − 4)!

− · · · =

n!(n − 1)!

r!(n − r)!

2

2. Dokaz odhad poctu Spernerovych systemov An, pricom Tn =

n

bn/2c

:

2

Tn < A

n <

2Tn

Tn

3. Student riesi ulohy v priebehu roka. Kazdy den riesi (neznamena, ze vyriesi) aspon jednu ulohu.
Aby nebol pretazeny, v kazdom tyzdni vyriesi najviac 12 uloh. Dokazte, ze existuje niekolko po
sebe iducich dni, pocas ktorych student vyriesi 20 uloh.

Riešenie.
Takto zadané to neplatí, napr. keď študent každý pondelok vyrieši 12 úloh.
Keby tam bolo ”každý deň vyrieši aspoň 1 úlohu”, asi to už platí, aj keď viac
by sa mi páčilo ešte zmeniť ”každý týždeň” na ”každých po sebe idúcich 7
dní”.

4. Dokazte, ze mnoziny {0, 1}N a {0, 1, 2}N maju rovnaku mohutnost.

5. Nech A,B su konecne mnoziny, |A| = n, |B| = m. Dokaz:

a) ak A a B su disjunktne, tak |A ∪ B| = n + m

b) |A × B| = nm

c) |AB] = nm

6. Nech X je konecna mnozina. Potom plati:

a) Ak f : X → X je injekcia, tak f je bijekcia.

b) Ak f : X → X je surjekcia, tak f je aj injekcia.

Riešenie.

a) Sporom, nech to nie je bijekcia, potom ∃a ∈ X, na ktorý sa nič nezobrazí.

Teda máme |X| vzorov, |X| − 1 obrazov. Z Dirichletovho princípu sa
niektoré 2 vzory musia zobraziť na ten istý obraz, a teda f nie je injekcia.

b) Sporom, nech to nie je injekcia. Potom ∃a, b ∈ X; f (a) = f (b). Potom ale

musí byť f (X \{a, b}) = X \{f (a)}. To sa ale nedá, lebo množina obrazov
je väčšia ako množina vzorov. (Ľudsky: Ak sa dva prvky zobrazia na ten
istý, tak na niektorý iný sa nezobrazí nič.)

1. Pocet permutacii n prvkov takych ze ai+1 nenasleduje bezprostredne za ai.

Riešenie.
Vraj výsledok (neoveril som, ale vyzerá ± dobre):

n! −

n−1

X

i=1

(−1)

i+1

n − 1

i

(n − i)!

2. Je danych k prvkov v riadku, dokazte ze existuje medzi nimi postupnost po sebe iducich prvkov
takych, ze ich sucet je delitelny k.

Riešenie.
Všimnime si súčty a1, a1 + a2, . . . , a1 + . . . + ak. Ak je niektorý z nich deliteľný
k, vyhrali sme. V opačnom prípade sú všetky zvyšky po delení k z množiny
{1, . . . , k − 1}. Z Dirichletovho princípu dávajú 2 z nich rovnaký zvyšok. No a
stačí tie dva od seba odčítať.

3

3. Dokazte pomocou indukcie pre n ze mohutnost komplementu zjednotenia n mnozin sa rovna
Pn

k=0(−1)

k Sk

4. Nutna a postacujuca podmienka existencie viacerych reprezentantov. (Tento priklad je v tych
lajstrach s prikladmi.)

Riešenie.
Podmienka je: Aby mala každá množina r reprezentantov, treba a stačí, aby
zjednotenie každých k množín malo aspoň rk prvkov.
Insight (Pozn. autora: Nezľaknite sa, ak nerozumiete. Možno pochopíte pred
štátnicami.): Predstavme si bipartitný graf, vrcholy na jednej strane budú naše
množiny, vrcholy na druhej strane ich prvky, hrana medzi nimi je iff prvok patrí
do množiny. Dajme každej hrane kapacitu 1, pridajme odtok, z každého prvku
doň hranu s kapacitou 1, zdroj, z neho do každej množiny hranu s kapacitou r.
Potom hľadaný systém reprezentantov existuje práve vtedy, keď v tomto grafe
existuje tok s hodnotou rn, kde n je počet množín. Práve uvedená podmienka
je ekvivalentná s tým, že každý rez v našom grafe má kapacitu aspoň rn.
(V jednej časti rezu bude k vrcholov zodpovedajúcich množinám, tie prispejú
aspoň rk hranami s kapacitou 1, v druhej zvyšné, tie prispejú n − k hranami
s kapacitou r.)

5. Bijekcia N

3 → N.

6. Dokaz Konigovej vety.

Riešenie.
Insight (Pozn. autora: Nezľaknite sa, ak nerozumiete. Možno pochopíte pred
štátnicami.): Na tú maticu sa môžeme dívať ako na maticu susednosti bipar-
titného grafu (ak ai,j = 1, i-ty vrchol prvej a j-ty vrchol druhej partície sú
spojené hranou). Königova veta vlastne hovorí, že v ľubovoľnom bipartitnom
grafe je veľkosť najmenšieho vrcholového pokrytia rovnaká ako veľkosť najväč-
šieho párovania.
Z každej hrany párovania musíme do pokrytia vybrať aspoň 1 vrchol. A prečo
toľko stačí? Nájdime maximálne párovanie = maximálny tok. Z každej hrany
párovania vyberieme ”spodný/pravý” vrchol (vzdialenejší od zdroja), ak doň
vedie zlepšujúca cesta (cez nejaký párovaním nepokrytý ”horný/ľavý” vrchol,
ktorý musíme pokryť) a ”horný/ľavý” vrchol inak.

Ustna: Dokazat Eulerovu vetu o particiach. Definicia grafu.

4