Riesenia uloh

Pokus o riešenia úloh z diskrétnej matiky

(prvý semester)

(c) Mišo Forišek 1999

Kombinatorika

Papier začínajúci “Nech m,n sú celé. . .”

1. Každá taká cesta zodpovedá postupnosti núl a jednotiek, v ktorej je práve

m núl. Takých postupností je ale zjavne

m+n

n

2. Každá matica m × n požadovaného tvaru je jednoznačne určená svojou

podmaticou (m − 1) × (n − 1), lebo zvyšné čísla sa dajú jednoznačne určiť.
Preto všetkých matíc požadovaného tvaru je 2(m−1)(n−1).

3. Matický alebo fyzikálny navštevuje 35 − 10 = 25 ľudí, keďže 20 matický,

11 fyzikálny, tak oba navštevuje 20 + 11 − 25 = 6 ľudí. A teda iba matický
20 − 6 = 14 ľudí.

4. Špeciálny prípad 5.

5. Kombinatorickou úvahou: Koľkými spôsobmi môžme vybrať k objektov

spomedzi m + n rôznych ?

m+n

k

. Ale keď si objekty rozdelíme na 2 kôpky,

na jednej m, na druhej n, tak z jednej vyberieme i

n

i

spôsobmi, z druhej

(k − i)

m

k−i

spôsobmi, toto zrátame cez ∀i, mame sumu na ľavej strane,

q.e.d.

5’. Indukciou podľa q.

Pre q = 1 je

n

m

= n

m

, čo dosť očividne platí. Teraz nech P n1

m1

· n2

m2

·

. . . ·

nq

mq

= n1+...+nq

m

Dokážme, že to platí aj pre q + 1. Je:

X

m1+...+mq+1=m

q+1

Y

i=1

ni

mi

=

X

m1+...+mq+1=m

nq+1

mq+1

·

q

Y

i=1

ni

mi

=

=

m

X

k=0





nq+1

k

·

X

m1+...+mq+1=m−k

q

Y

i=1

ni

mi





= (podľaind.predp.) =

=

m

X

k=0

nq+1

k

·

n1 + . . . + nq

m − k

= (podľa úl. 5.) =

n1 + . . . + nq+1

m

čo bolo treba dokázať. Ešte pre tých, čo sa zdesia už pri pohľade na tú
sumu v zadaní - ide o súčet CEZ VŠETKY q-tice (m1, . . . , mq), ktoré
spĺňajú podmienky zo zadania. Ide vlastne o to isté ako v 5. - keď máme
vybrať m predmetov spomedzi n1 + . . . + nq, tak si ich rozdelíme na q

1

kôpok, na prvú dáme n1, atď., no a teraz môžme tých m vybrať len tak,
že z 1. kôpky vezmeme m1, atď, pričom mi musia spĺňať podmienky pod
sumou. Aj toto je korektný dôkaz (komb. úvahou), len neviem, nakoľko ho
bude E.T. ochotný zožrať.

6.

a) V každom stĺpci je jedna, pre tú v prvom máme n možností, pre

druhú (n − 1), . . . takže spolu n!.

b) Pre prvú máme n2 možností, pre druhú (n − 1)2, lebo 1 riadok a 1

stĺpec sú obsadené, . . . takže spolu n2.(n − 1)2. · · · .12 = (n!)2.

c) Analogicky, vyjde

Qn−1

i=0 (m − i), resp. to celé na druhú, pre m < n to

je zjavne 0 (v súčine je nulový člen), takže to funguje aj pre ne.

7. Jednoduché, len pracné. Pre istotu hodnoty sedmových karát : D = 2, H =

3, K = 4, 7 = 7, 8 = 8, 9 = 9, 10 = 10, A = 11. A je 21 = 11 + 8 + 2 =
11 + 7 + 3 = 10 + 9 + 2 = 10 + 8 + 3 = 10 + 7 + 4 = 9 + 8 + 4, v každom
z týchto prípadov 43 = 64 možností, . . . = 9 + 9 + 3, to je

4
2

· 4 = 24

možností, . . . = 7 + 7 + 7, to je

4
3

= 4 možnosti, spolu 6.64 + 24 + 4 = 412

možností.

8. A a B majú dokopy 18 kníh. Tie spomedzi 27 vyberieme

27
18

spôsobmi.

Medzi A a B ich rozdelíme 218 spôsobmi, lebo každú môžeme dať A alebo
B. Tým je už určené aj čo dostane C. Preto spolu to je

27
18

· 218 možností.

9. N mužov usadíme (n − 1)! spôsobmi - prvého posadíme kamkoľvek, ostat-

ných polohu už určujeme podľa neho, idú len na ’nepárne’ miesta. Potom
rozsadíme ženy na zvyšné miesta n! spôsobmi, spolu n!(n − 1)! spôsobov.

10. Postupne vyberajme, ktoré guličky dáme do 1., 2., . . . , k. škatule. Do prvej

máme pre 1. guličku n možností, pre 2. (n − 1) možností, . . . , pre n1
n − n1 + 1 možností. Pre prvú guličku z ďalšej krabice máme n − n1
možností, atď. Takže dokopy by to bolo n! možností, ale v rámci každej
krabice sme zarátali ∀ usporiadania guličiek, ktorých je pre i. krabicu ni!.
Takže všetkých rozdelení je

n!

n1!.n2!.···.nk!

11. Keďže guličky sú rovnaké, môžme prvých s škatúľ naplniť hneď na za-

čiatku, ostane nám k = n −

P ai guličiek a l = m − s krabíc, to je

ekvivalentné s počtom riešení rovnice x1 + ... + xl = k ∧ xi ≥ 0. Takže
máme

k+l−1

k

možností.

12. Na začiatku podávame guličky tam, kam treba, ostane nám k = n −

P ai

guličiek, ktoré máme ľubovoľne rozmiestniť do m krabíc, to ide

m+k−1

k

spôsobmi.

13. Predstavme si n objektov v rade. Medzi nimi je n − 1 medzier. Keď do

k − 1 z nich dáme priehradku, rozpadne sa nám to na k častí, ktoré určujú
nejaký usporiadaný rozklad. Zjavne keď dáme priehradky na iné miesta,
dostaneme rôzne rozklady. Naopak, každému rozkladu vieme nájsť prí-
slušné rozdelenie priehradok. Preto je rozdelení priehradok a usp. rozkla-
dov rovnako, teda

n−1
k−1

.

2

14. Koľko čísel od 1 po n je deliteľných p? b

n

p c. Všetkých súčinov je n

k , tých,

ktoré nie sú deliteľné p, je (n − b

n

p c)

k , takže zvyšné sú deliteľné p.

15. Z binomickej vety pre (1 + 1)n.

16. Rozoberieme 6 prípadov podľa toho, koľko žien vyberieme spomedzi zná-

mych muža. (potom je jasné, koľko vyberáme ostatných). Mlčky treba
predpokladať, že muž a žena nemajú spoločných známých :-)

17. Pre prvého 8 možností, pre druhého 7, atď., každé rozostavenie sme zará-

tali 8×, preto je to 7!.

18. Keď tých 5 kníh vyberieme, ostatné sa tým rozdelia na 6 častí, z ktorých

stredné 4 sú neprázdne. Máme teda zistiť, koľko má riešení rovnica x1 +
. . . + x6 = 12 − 7 = 5 za podmienok x1, x6 ≥ 0 ∧ x2, . . . , x5 > 0. To je
ekvivalentné s rovnicou x1 + . . . + x6 = 9 ∧ xi > 0 o ktorej vieme, že má

8
5

= 8.7.6

3.2.1 = 56 riešení.

19.

a) Buď sú obe čísla párne, alebo obe nepárne, v oboch prípadoch máme

15

2

možností, spolu 15.14 = 210 možností.

b) Buď dávajú všetky tri rovnaký zvyšok po delení 3, to sú 3 prípady,

v každom

10

3

možností, alebo dve z nich dávajú rôzny. Rozobratím

prípadov zistíme, že jediná možnosť je tá, že jedno dáva zvyšok 0,
jedno 1 a jedno 2, tu je teda 103 možností, spolu 3.

10

3

+ 103 = 1360

možností.

20. Pre Joža a Ďura sú len 3 možnosti – buď ide Jožo 5., alebo 6., alebo 7., v

jednotlivých prípadoch ide Ďuro 4., 5. alebo 6. Pre Jana máme zakaždým
5 možností, kedy môže ísť. Preto dokopy môžu ísť na skúške 3.5 = 15
spôsobmi. (A ôsmimi spôsobmi na nej dopadnúť :)

Papier začínajúci “Nájdite súčet všetkých. . .”

21. Takých čísel je 24, 6 má na mieste jednotiek 1, 6 má 2, atď., analogicky

na mieste desiatok a stoviek, preto ich súčet je (100 + 10 + 1).(6.1 + 6.2 +
6.3 + 6.4) = 6660.

22. Všetkých 4 je

n

3

. Z nich nevyhovujú tie, ktoré majú niektoré dva vrcholy

susedné. Tých je n.(n − 2), lebo susednú dvojicu vyberieme n spôsobmi,
zvyšný vrchol n−2 spôsobmi. Tu sme ale dvakrát zarátali všetky tie, ktoré
majú všetky tri vrcholy idúce po sebe. Takých je zjavne n. Takže výsledný
počet je

n

3

− n(n − 2) + n, pre n = 3 treba povedať, že je to 0, lebo tam

vzniká chaos pri rátaní. . .

23. Označme strany a,b,c tak, aby a ≤ b ≤ c. Potom z 4 nerovnosti ⇒

c <

40

2 = 20, zároveň z a ≤ b ≤ c ⇒, že 40 = a + b + c ≤ c + c + c = 3.c ⇒

c ≥

40

3 , pre každú možnosť vieme nájsť max. a min. hodnotu b, (lebo

b ≤ c ∧ 40 − c = a + b ≤ 2.b), každej zodpovedá 1 hodnota a, zrátame,
hotovo.

3

24. Spomedzi 000 . . . 999 začína jednotkou 100, zo zvyšných má na 2. mieste

jednotku 9.10 = 90, zo zvyšných má na 3. mieste jednotku 9.9 = 81 a
navyše ostala 1000 ⇒ 1 obsahuje 100 + 90 + 81 + 1 = 272 čísel.

25. Súčet všetkých koeficientov dostaneme na pravej strane, keď za všetky ai

dosadíme 1. Vtedy ale ľavá strana je kn.

26. Platí : k-ty člen je

100

k

.(

√

2)k.(

4

√

3)100−k. Ľahko ukážeme, že toto číslo

je rac. práve vtedy, keď sú rac. (

√

2)k a (

4

√

3)100−k. A to je zasa vtedy, keď

2|k ∧ 4|(100 − k). Preto je racionálnych členov 26.

27. Cez k.

n
k

= n. n−1

k−1

a (1 − 1)n−1.

28-29. Asi cez 25.

30. Platí 1n = (

1+x

2

+

1−x

2

)n = (

1+x

2

)n+(

1−x

2

)n+

Pn−1

i=1

n

i

·( 1+x

2

)i·(

1−x

2

)n−i ≥

(

1+x

2

)n + (

1−x

2

)n, z čoho vynásobením 2n máme dokaz. nerovnosť.

31. To je na samostatný papier. . .

32. Platí

m

k

m−k

n−k

=

m!.(m−k)!

k!.(m−k)!.(m−n)!.(n−k)! =

m!

k!.(n−k)!.(m−n)! =

m!.n!

n!.(m−n)!.k!.(n−k)! =

m

n

n
k

, konštantu m

n

vyberieme pred sumu a ostane

nám zjavná 0.

33-34. Pre m = 2 ∧ n = 1 je to 3, takže neplatí ani 1 z tých rovností. . .

35. Športujú 15 chlapci s dobrým prospechom, t.j. 3 so zlým. Športuje 11

žiakov so zlým prospechom, preto športuje 8 dievčat so zlým prospechom.
Dievčat so zlým prospechom je však len 6, preto je v správe chyba.

36. Je ich n − ϕ(n) = 210 − 210 · (1 −

1
2 ) · (1 −

1
3 ) · (1 −

1
5 ) · (1 −

1
7 ) =

210 − 210 ·

1
2 ·

2
3 ·

4
5 ·

6
7 = 210 − 48 = 162.

37. Koľko je del. 2 ? b

100

2 c = 50. Analogicky tromi je del. 33, piatimi 20. Koľko

nie je deliteľné 2, 3 ani 5 ? 100 − 50 − 33 − 20 = −3 ??? Nie, lebo sme 2x
odrátali tie, ktoré sú del. dvomi z nich a 3x tie, čo sú del. všetkými tromi.
Tie ešte musíme prirátať. 2 a 3, teda 6 je del. 16, 2 a 5 10, 3 a 5 6, tie
prirátame, máme −3 + 16 + 10 + 6 = 29, ale opäť sme 3x prirátali tie, čo sú
del. všetkým, ešte ich na záver musíme odrátať, sú 3, takže spomedzi čísel
1 . . . 100 ich 29 − 3 = 26 nie je del. 2, 3 ani 5. Práve (trochu ťažkopádne a
rozsiahlo, ale to len kvôli zrozumiteľnosti) použitý princíp sa volá princíp
zapojenia a vypojenia, alebo noblesnejšie princíp inklúzie a exklúzie.

38. Je

n−1

0

+ n

1

+ . . . + n+m−1

m

= n

0

+ n

1

+ . . . + n+m−1

m

= n+1

1

+ . . . +

n+m−1

m

= . . . = n+m−1

m−1

+ n+m−1

m

= n+m

m

. Alebo indukciou podľa m.

39. Cez i.

n

i

= i ·

n!

i!.(n−i)! = n ·

(n−1)!

(i−1)!.(n−i)! = n.

n−1

i−1

, pre 0 je i. n

i

= 0,

takže tento člen môžme vynechať.

4

40.

- Bez kombinatorickej úvahy : z binomickej vety pre ((m − 1) + 1)n s

využitím

m+n

m

= m+n

n

.

- Komb. úvahou : Vyberajme n prvkov spomedzi m, záleží na poradí,

môžu sa opakovať. Koľko je takých, v ktorých je k jedničiek ?

n
k

·

(m − 1)n−k, keď to zrátame cez všetky k, dostaneme počet variácii s
opak. n. triedy z m prvkov, ktorých je mn.

41. Prienik každej s povrchom gule je rovníková kružnica (t.j. kružnica s rov-

nakým polomerom ako guľa). Zo zadania ⇒, že žiadne 3 kružnice nemajú
spoločný bod. Keď máme jednu kružnicu, tá delí povrch na 2 časti. Nech
n kružníc delí povrch na P (n) častí, na koľko ho môže deliť n + 1 kružníc
? Keď pridáme (n + 1). kružnicu, tá pretne už exist. n v 2n bodoch. Tie
ju rozdelia na 2n úsekov. Každý z týchto úsekov rozdelí jednu z už exis-
tujúcich častí na 2. Teda pribudlo presne 2n častí, čiže ich je P (n) + 2n.
Teraz už nie je až také ťažké spočítať/uhádnuť a dokázať indukciou vzorec
P (n) = n.(n − 1) + 2 = n2 − n + 2.

42. Položíme n = r + m, máme 38.

43. Pre k <

n−1

2

je

n

k+1

=

n!

(k+1)!.(n−k−1)! =

n!

k!.(n−k)! ·

n−k

k+1 =

n
k

· n−k

k+1 >

n
k

,

druhá nerovnosť analogicky.

Papier začínajúci “Nájdite maximum spomedzi. . .”

44. Z 43. vyplýva, že je to

n

b n

2 c

.

45.

p
k

je celé, platí p

k

=

p!

k!.(p−k)! , p delí čitateľa, nedelí menovateľa, z toho

vyplýva, že delí

p
k

.

46. Prenásobíme n + 1 a použijeme

a

b ·

a−1

b−1

=

a

b

a binomickú vetu pre

(1 + 1)a.

47. Triviálna indukcia

48. Indukciou cez vzorec 1 + . . . + n =

n.(n+1)

2

.

49. Je

1

(a+i−1)(a+i) =

1

a+i−1 −

1

a+i , preto cela suma vyzerá

1
a −

1

a+1 +

1

a+1 −

1

a+2 +

· · · − 1

a+n z čoho sa nám vymlátia dvojice, ostane

1
a −

1

a+n =

(a+n)−a

a(a+n)

=

n

a(a+n)

50. O5 trápna indukcia podľa n.

51-52. Indukcia až to bolí. . .

53. Indukcia. 2. krok je :

n+1

Y

i=1

(n + 1 + i) =

(2n + 2)(2n + 1)

n + 1

·

n

Y

i=1

(n + i) = 2.(2n + 1).2

n.

n

Y

i=1

(2i − 1) =

5

= 2

n+1.

n+1

Y

i=1

(2i − 1)

Papier začínajúci “Ak A, B sú konečné. . .”

54. Pre každý z m prvkov máme n možností, na čo ho zobraziť. . .

55. Pre prvý máme n možností, pre druhý n − 1, . . .

56-57. Priamo dosadíme do 55.

58. Ten hrozný súčin je maskované

n
k

.

59. A toto je maskované

P

n

i

= 2n.

60.

a) Z definície.

b) Z a).

c) Z definície.

d) Viď 5.

e) Z a)

f) Inými slovami dokážte binomickú vetu. Napr. indukciou.

g) Z f) pre x = −1.

h) Viď 32.

61-63. Sú riešené na papieroch, čo sme fasovali. . .

Papier začínajúci “Nech k, n1, . . . , nk . . .”

64. Riešené na papieri, čo sme dostali.

65. Vyplýva z 64., len to ešte treba predeliť všetkými usporiadaniami tých k

podmnožín (keďže na ich poradí nám nezáleží), ktorých je k!.

66.

(1) Viď 39.

(2) Analogicky ako (1).

(3)

P(2k + 1)

n
k

= 2. P k n

k

+ P n

k

(4) Viď 46.

(5) Presne na to isté kopyto ako (4).

(6) Indukciou.

1 + · · · +

1

n + 1

= (1 + · · · +

1

n

) +

1

n + 1

= (z IP a podúlohy (5)) =

=

n

X

k=1

(−1)

k−1 ·

1

k

n

k

+

n

X

k=0

(−1)

k

1

k + 1

n

k

=

n

X

k=1

(−1)

k−1 ·

1

k

n

k

+

6

+

n+1

X

k=1

(−1)

k−1 1

k

n

k − 1

=

(−1)n

n + 1

+

n

X

k=1

(−1)

k−1 1

k

n

k

+

n

k − 1

=

=

(−1)n

n + 1

+

n

X

k=1

(−1)

k−1 1

k

n + 1

k

=

n+1

X

k=1

(−1)

k−1 1

k

n + 1

k

(7) Cez (1+1)n a (1−1)n, v jednom prípade sa to sčíta, v druhom odčíta.

(8) Cez vhodný súčet, resp. rozdiel výrazov (1 + 1)n, (1 − 1)n, (1 + i)n a

(1 − i)n (treba zvoliť znamienka tak, aby ostali len správne členy).

Dve chuťovky na záver kombinatoriky. . .

Úloha 31.

Taká úplne nenápadná úloha, skrytá v dave, ale teda tyč na pohľadanie. Po-
ložme si najskôr otázku, koľko je permutácii, kde nič nie je na svojom mieste
(t.j. špec. prípad r = 0). Označme tento počet P (n). Je P (1) = 0, P (2) = 1.
Koľko je P (n) ? Ak je 1 prehodená s nejakým iným prvkom (t.j. 1 je k-ta a k
je prvé), tak máme pre zvyšné prvky P(n-2) možností, zároveň (n-1) možností,
ktorý prvok je k. Ak 1 nie je prehodená s inou, keď ju vymeníme s tým, čo je
na 1. mieste, na zvyšných n − 1 miestach dostaneme prehádzanú (n − 1)-ticu,
zakaždým sme mali n − 1 možností, kde mohla 1 pôvodne byť. Spolu teda máme
P (n) = (n − 1).(P (n − 1) + P (n − 2)). To je síce pekné, a pre naše účely aj
poučné, ale aj na pažu.
Potrebovali by sme explicitný vzorec. (t.j. taký, do ktorého sa dá priamo dosa-
diť.) Na to použijeme zaužívané kombinatorické delo, ktoré sme síce nemali tú
česť preberať, ale príklady naň dá E.T. na skúške ako vidieť s radosťou. Princíp
inklúzie a exklúzie. Ten v takom Tomanovskom množinovom zápise vyzerá :
Majme množiny M1, . . . , Mn, potom |

S Mi| = P |Mi| − P

i6=j |Mi ∩ Mj | + . . . =

n

X

k=1





(−1)

k−1 ·

X

i1<...<ik

k

\

j=1

Mi

j





Čo vlastne znamená toľkoto : koľko prvkov má prienik n množin ? To je počet
prvkov prvej + . . . + počet prvkov n., ale 2-krát sme zarátali každý prvok, ktorý
je v dvoch z nich, takže odrátame prieniky všetkých dvojíc množín. Prvky, ktoré
sú v troch sme

3
1

-krát prirátali, 3

2

-krát odrátali, takže vôbec nie sú zarátané,

musíme ich prirátať, atď. (Toto nie je dôkaz, len také intuitívne zdôvodnenie,
čo to hovorí a prečo to funguje.)
No a ako to použijeme v našom prípade ? Nech Mi je množina všetkých per-
mutácií, ktoré majú na i-tom mieste i. Čo je zjednotenie týchto množín ? To sú
práve všetky nevyhovujúce permutácie. No a keď si ešte uvedomíme, že Mi má
(n − 1)! prvkov,

Tk

j=1 Mij je množina všetkých permutácií, ktoré majú k miest

pevne určených, má teda (n − k)! prvkov. S tým už môžme rátať:

P (n) = n! −

n

X

k=1





(−1)

k−1 ·

X

i1<...<ik

k

\

j=1

Mi

j





=

7

= n! +

n

X

k=1

(−1)

k ·

n

k

· (n − k)!

=

n

X

k=0

(−1)

k ·

n

k

· (n − k)!

Možno sa teraz zlomyseľne pýtate, načo vlastne bola tá prvá úvaha. Jednoducho
- ak by E.T. nechcel zožrať inklúziu a exklúziu bez dôkazu, tak sa naňho vytiahnu
vzťahy z prvej úvahy, povie sa tento vzorec a indukciou podľa n sa dokáže, že
vyhovuje tomu vzťahu a keďže tým je P (n) jednoznačne určené, je to vlastne
dôkaz toho vzťahu.
No a koľko je permutácií s práve r prvkami na svojom mieste ? Prvky na svojich
miestach vyberieme

n

r

spôsobmi, zvyšné tvoria prehádzanú permutáciu s n − r

prvkami, takže je to

n

r

· P

n−r
k=0

(−1)k

n−r

k

(n − r − k)!

No a keď už sme takí rozbehnutí, tak rovno chuťovka číslo dva. (dve ? jed-

noducho 2 !)

Angličania a Francúzi.

Pre tých, čo nevedia, o čom je reč: máme n Angličanov, m Francúzov. Koľkými
spôsobmi ich možno postaviť do radu tak, aby každý mal vedľa seba aspoň
jedného krajana ?
Zabudnime najskôr na to, že Angláni aj Francúzi sú individuality, teda každý
iný, ešte sa aj nejako volajú, zaujímajme sa o nich najskôr ako o farebné guličky.
Koľkými spôsobmi rozdelíme Angličanov na k skupín tak, aby v každej boli
aspoň dvaja ? To je ekvivalentné s rovnicou a1 + . . . + ak = n ∧ ∀i; ai ≥ 2, čo
je zase ekviv. s a0

1 + . . . + a

0
k = n − k ∧ ∀i; a

0
i = ai − 1 ≥ 1, o ktorej vieme, že

má

n−k−1

k−1

riešení. A ako medzi nich narvať m Francúzov ? Tí musia byť v

každej medzere, teda ich skupín musí byť aspoň k − 1, ale zároveň ich môže byť
najviac n + 1, lebo už môžu pribudnúť len dve skupiny – na začiatku a na konci.
Ak máme k − 1 skupín Francúzov, na to máme analogicky

m−k

k−2

možností a

je jasné, ako ich tam postavíme. Podobne ak je Francúzov k + 1 skupín, na to
máme

m−k−2

k

možností a opäť je jediná možnosť, ako ich tam postaviť. Ak ich

je k skupín, možností je

m−k−1

k−1

, a postaviť ich tam môžme dvomi spôsobmi

– buď je jedna skupina na začiatku, alebo je jedna na konci. Dokopy to pre
KAŽDÉ rozostavenie k skupín Angličanov dáva

m−k

k−2

+ 2 · m−k−1

k−1

+ m−k−2

k

vyhovujúcich rozostavení. No a hľadaný počet by bol potom súčet tohto cez
všetky k, teda:

∞

X

k=1

n − k − 1

k − 1

·

m − k

k − 2

+ 2 ·

m − k − 1

k − 1

+

m − k − 2

k

To ale ešte stále vyzerá divne kvôli tej sume do ∞ a ešte sme nezarátali rozlíši-
teľnosť ľudí. Keď ale máme nejaké usporiadanie, kde máme povedané, kde stoja
Angličania a kde Francúzi, tak konkrétnych ľudí naň môžme postaviť n!.m! spô-
sobmi – Angličanov rozmiestnime na ich miesta n! spôsobmi a Francúzov na ich
miesta následne m! spôsobmi. No a z tej sumy je nenulových len prvých b

n

2 c

členov, lebo pre k > b

n

2 c je k − 1 > n − k − 1, teda

n−k−1

k−1

= 0, čiže aj celý

8

sčítanec je 0. Výsledok úlohy teda je:

n!.m!.

bn/2c

X

k=1

n − k − 1

k − 1

·

m − k

k − 2

+ 2 ·

m − k − 1

k − 1

+

m − k − 2

k

Množiny & co.

Vybrané z 3 papierov U.x.yy

U-2-20.

⇒: Nepriamo. Nech A 6⊆ C. Potom ∃x; x ∈ A ∧ x 6∈ C. Potom ale x ∈

(A ∪ (B ∩ C)) ∧ x 6∈ ((A ∪ B) ∩ C).

⇐: Nech A ⊆ C. Potom ak x ∈ A, tak x ∈ do oboch množín, ak x 6∈ A,

tak x ∈ (A ∪ (B ∩ C)) ⇔ x ∈ (B ∩ C) ⇔ x ∈ B ∧ x ∈ C ⇔ (x ∈
A ∨ x ∈ B) ∧ x ∈ C ⇔ x ∈ ((A ∪ B) ∩ C)

U-2-22. Sporom. Nech A 6= B. Potom BUNV ∃x; x ∈ A ∧ x 6∈ B. Preto x ∈

B ∪ X ⇒ x ∈ A ∪ X ⇒ x ∈ X
Potom ale x ∈ B ∩ X ⇒ x ∈ A ∩ X ⇒ x ∈ A, čož hľadaný spor.

U-2-24.

⇒: A ∈ A ∪ B = B ∪ C, ostatné rovnako.

⇐: Ak x 6∈ A ∩ B ∩ C, tak x 6∈ A ∪ B ∧ x 6∈ B ∪ C ∧ x 6∈ C ∪ A

Inak BUNV nech x ∈ A. Je A ⊂ B ∪ C ⇒ x ∈ B ∪ C a zjavne aj
x ∈ A ∪ B ∧ x ∈ A ∪ C.

Všeob. úvaha Drvivá väčšina rovností množinových vzťahov sa dá dokazovať tak, že

dokážeme, že x patrí do výrazu na ľavej strane práve vtedy, keď do výrazu
na pravej (a takto si to teda prevedieme na ekvivalentnú úlohu s výrokmi,
ktorú ľahko vieme riešiť.)
Demo: Dokážte: A ∪ B = A ∪ (B − A)
x ∈ A ∪ B ⇔ x ∈ A ∨ x ∈ B ⇔ x ∈ A ∨ (x 6∈ A ∧ x ∈ B) ⇔ x ∈ A ∨ x ∈
(B − A), q.e.d.

Cantor-Bernsteinova veta

1. Má byť prosté a na, inými slovami nájdite bijekciu.

a) x →

1

x

b) Premietneme os x na kruh so stredom v (0, 1) a polomerom 1 so

stredom premietania v (0, 2).

c) Priamke y = ax + b priradíme pre a 6∈ N0 dvojicu (a, b), pre a ∈ N0

dvojicu (a + 1, b), priamke x = c dvojicu (0, c).

d) ??? Čo sú paraboly v rovine ? Musia mať os rovnobežnú s osou y? Asi

nie. . . Ale vždy sa to dá tak, že ju popíšeme nejakými 4 . . . 5 číslami,
a nájdeme bijekciu medzi R3 a R4 (alebo 5), čo je ekvivalentné s bi-
jekciou medzi R a R2 a tá sa dá spraviť tak, že pred aj za desatinnou
čiarkou dávame cifry striedavo z jedného a druhého čísla.

9

e) Kruh zobrazíme na (stredx, stredy, polomer).

f) Keď si to nakreslíme, vidíme, že pôvodná množina tvorí kruh a vý-

sledná štvorec jemu opísaný. Bod (0, 0) nech sa zobrazí sám na seba.
Ostatné body zobrazíme takto : spravíme polpriamku so začiatkom
v (0, 0), prechádzajúcu daným bodom. Označme náš bod A, bod, v
ktorom polpriamka pretne štvorec B. Potom obraz bodu A je ten bod
C polpriamky, pre ktorý je |OA| =

|OC|
|OB| . (Teda celú úsečku ležiacu

na tejto polpriamke “natiahneme” tak, aby dočiahla až po štvorec)

g) Podobne ako b), len tentokrát premietame guľu z bodu (0, 0, 2) na

rovinu z = 0.

2. Treba vlastne nájsť injektívne zobrazenie A do B. Vo všetkých prípadoch

sa presvedčte, že uvedené zobrazenie je naozaj prosté !

a) x →

x+20

miliónpäť

b) Postupnosť {an}

∞

n=0 zobrazíme na postupnosť {bn}

∞

n=0, kde bi =

a1

2i .

Potom je 0 <=

P bi <= P

1

2i = 2, preto

P bi konverguje.

c) Každý člen postupnosti A zapíšeme pomocou dvoch členov B (vyšší

a nižší bit :)

d) Pre jednoduchosť nech sú N od jednotky (ak ich chce E.T. od nuly,

treba ich najskôr zobraziť každé na o 1 väčšie). Teraz vieme využiť
to, že binárny zápis každého prir. čísla začína jednotkou. Preto každé
prirodzené číslo vieme zakódovať tak, že najskôr zapíšeme toľko núl,
koľko miest má jeho binárny zápis, a potom binárny zápis príslušného
čísla.

e) (x, y) → (

x

1999 ,

y

2000 )

3. Treba nájsť injekcie z A do B aj z B do A.

a) Trocha naokolo - ako v 2.d) ukážeme, že majú obe rovnakú mohutnosť

ako {0, 1}N . Ozaj, keby to niekoho zaujímalo, tak N N

m je množina

všetkých postupností čísel 0, 1, . . . , m.

b) OOOK ??? čo je to reálna ohraničená spojitá f-cia ? Ak je to nor-

málna funkcia (−1, 1) → R, tak injekcia z A do B je v zadaní, opačná
mi uniká. . .

c) Jeden smer je zjavný, v opačnom zoberieme každý prvok postupnosti

reálnych čísel, arkus tangensom ho zobrazíme na (−

π

2 ,

π

2 ), a ten in-

terval potom uťapkáme na (0, 1).

d) To isté, len to robíme s funkčnou hodnotou.

e) Postupnosť {an}

∞

n=0 zobrazíme na postupnosť {bn}

∞

n=0, kde b1 =

a1 ∧ bn+1 = bn + an+1.

f) Oba smery ako v 2.e).

4. Smrť moja. . . sa mi už nechce. . .

10

A drobné upozornenia na záver

To, že niečo na týchto papieroch nesedí s tvojimi výsledkami, môže byť

zavinené tromi základnými chybičkami krásy:

• - Je to to isté, len to máš ináč zapísané. To by až tak nevadilo, na skúške

určite nie, len to treba do skúšajúceho dosť dlho tlačiť.

• - Máš to zle, môžeš sa biť po hlave, aká/ý si blbá/ý (čo budeme diskri-

minovať feministky tým, že vždy sa skôr píše mužský rod, že, dáme občas
skôr ženský . . . :)

• - Mám to zle ja. Aj to sa môže stať, nik nie sme neomylný. V tomto prípade

však STRIKTNE odporúčam akékoľvek bitie vynechať, ale budem rád, keď
sa mi o tom dá vedieť. . . (Pozn. po dvoch rokoch: momentálne už viem, že
tam nejaké chyby sú, ale mám ich srdečne v paži.)

Tieto papiere NEMAJÚ slúžiť ako náhrada za počítanie príkladov, ale na

kontrolu výsledkov a pomoc pri tých najväčších tyčiach, ktoré skoro nik nevie
:) . . .

11