Skusky

written by shelll, shelll.host.sk

1

*******************************************************************************************

1. Dokazte: n! ≤ 2 ·

n

2

n

vyuzite nerovnost: 2 ≤

1 +

1

n

n

< e

*******************************************************************************************

1

o

pre 0: 0! ≤ 2 ·

0
2

0

⇒ 1 ≤ 2

pre istotu aj pre 1: 1! ≤ 2 ·

1
2

1

⇒ 1 ≤ 1

2

o

IP: n! ≤ 2 ·

n

2

n

ma platit:

(n + 1)!

≤

2.

n + 1

2

n+1

z IP plati ⇒ (n + 1).n!

≤

(n + 1).2.

n

2

n

z predosleho riadku ⇒ (n + 1).2.

n

2

n

≤

2.

n + 1

2

n+1

·

1

2

· 2n+1

(n + 1).2.n

n

≤

(n + 1)

n+1

/ : (n + 1)

2.n

n

≤

(n + 1)

n

/ : n

n

2

≤

n + 1

n

n

2

≤

1 +

1

n

n

⇒ to plati z danej nerovnosti

z predosleho riadku ⇒ (n + 1).2.

n

2

n

≤

2.

n + 1

2

n+1

a kedze :

(n + 1).n!

≤

(n + 1).2.

n

2

n

tak aj :

(n + 1).n! ≤

(n + 1).2.

n

2

n

≤ 2.

n + 1

2

n+1

teda :

(n + 1)!

≤

2.

n + 1

2

n+1

a tymto je dokazana dana nerovnost, uz staci len obratit postup

written by shelll, shelll.host.sk

2

*******************************************************************************************

2. Dokazte: n! >

n

e

n

vyuzite nerovnost: 2 ≤

1 +

1

n

n

< e

*******************************************************************************************

1

o

pre 0: 0! ≤

0
e

0

⇒ 1 > 1 (neplati to, a preto to treba sparavit pre 1)

pre 0 to na pisomke nerobte a nepiste mu tam, ze to neplati !!!

pre 1: 1! ≤

1
e

1

⇒ 1 > 1

e

2

o

IP: n! >

n

e

n

ma platit:

(n + 1)!

>

n + 1

e

n+1

z IP plati ⇒ (n + 1).n!

>

(n + 1).

n

e

n

z predosleho riadku ⇒ (n + 1).

n

e

n

>

n + 1

e

n+1

.en+1

(n + 1).e.n

n

>

(n + 1)

n+1

/ : (n + 1)

e.n

n

>

(n + 1)

n

/ : n

n

e

>

n + 1

n

n

e

>

1 +

1

n

n

⇒ to plati z danej nerovnosti

z predosleho riadku ⇒ (n + 1).

n

e

n

>

n + 1

e

n+1

a kedze :

(n + 1).n!

>

(n + 1).

n

e

n

tak aj :

(n + 1).n! >

(n + 1).

n

e

n

>

n + 1

e

n+1

teda :

(n + 1)!

>

n + 1

e

n+1

a tymto je dokazana dana nerovnost, uz staci len obratit postup

written by shelll, shelll.host.sk

3

*******************************************************************************************

3. Dokazte:

n

k

k

<

n

k

<

3.n

k

*******************************************************************************************

lava nerovnica:

n

k

k

<

n

k

n

k

·

n

k

· · · · ·

n

k

·

n

k

|

{z

}

k

<

n

k

·

(n − 1)

(k − 1)

·

(n − 2)

(k − 2)

· · · · ·

(n − k + 2)

2

·

(n − k + 1)

1

a teraz ukazeme, ze

n
k

<

(n−i)
(k−i)

pre n > k > 1, pre i ≥ 1

n.k − n.i

<

n.k − i.k

i.k

<

i.n

k

<

n

podla predpokladu to plati, obratime postup a je to

Podla podmienky v zadani n > k > 1, co dava k ≥ 2, preto uz je zrejme, ze nerovnost c.1 plati (najprv
vykratime

n
k , potom pre i ≥ 2, i < k, plati, ze i-ty cinitel na pravej strane je > ako i-ty na lavej strane.)

prava nerovnost sa dokazuje tak isto, len mi to nevyslo, tak to tu nieje (mozno nabuduce :( )

written by shelll, shelll.host.sk

4

*******************************************************************************************

4. Kolkymi sposobmi mozme do matice m × n zapisat cisla 1 a −1 tak, aby sucin cisel bol
v kazdom riadku aj stlpci +1.

*******************************************************************************************

Obdlznik (n − 1) × (m − 1) z matice m × n (spodny riadok a pravy stlpec tam nepatria) vyplnime

lubovolne, to je 2(n−1).(m−1) sposobov lebo mame (n − 1).(m − 1) policok a do kazdeho mozeme dat
dva rozne prvky (+1, −1) a ukazeme, ze zvysny spodny riadok a pravy stlpec vieme zaplnit pre kazde
vyplnenie toho mensieho obdlznika a vzdy to vieme spravit jednoznacne.

Zoberme si nejaky riadok. Na posledne policko zapiseme 1, ak je jeho sucin 1, inac zapiseme −1

(v podstate to cislo, ktore zapisem na posledne miesto urcuje znamienko riadku). Takto vyplnime cely
uplne pravy stlpec. Uplne spodne policko (prave dolne z matice m × n) urcuje znamienko celej matice
(n − 1) × (m − 1) (sucin vsetkych jej prvkov). Takym istym sposobom vyplnime aj spodny riadok. Tu
uplne prave policko (opat prave dolne) tiez urcuje znamienko matice (m − 1) × (n − 1). Znamienko matice
(n − 1) × (m − 1) je rovnake a z toho vyplyva, ze vieme prave dolne policko vyplnit jendoznacne.

written by shelll, shelll.host.sk

5

*******************************************************************************************

5. Najdi bijekciu medzi kombinaciami s opakovanim k−tej triedy z n prvkov a kombinaciami
bez opakovania k−tej triedy z n + k − 1 prvkov.

*******************************************************************************************

Najprv priklad:
N = 20, K = 12
(1, 3, 3, 3, 7, 7, 10, 13, 14, 14, 15, 15) zobrazime na (1, 3, 7, 10, 13, 14, 15, 22, 23, 25, 29, 31) Ako to robime?
Tu kombinaciu s opakovanim si mozeme zapisat ako
(p1 . a1, p2 . a2, p3 . a3, ... , pm . am), kde {an} je vybrana rastuca podpostupnost postupnosti 1, 2, ...n ,
pi je pocet prvkov hodnoty ai v tej kombinacii s opakovanim, teda

P (pi) = K.

Snad sa vyjadrujem korektne a zrozumitelne (i ked pochybujem o obidvoch :) V nasom pripade {am} =
1, 3, 7, 10, 13, 14, 15 a {pm} = 1, 3, 2, 1, 1, 2, 2 No to uz vobec nie je korektne zapisane, ale budete to musiet
pre tentokrat tolerovat :)
No a zakoduje sa to ako (a1, a2, a3, ..., am, (n + 1)...(n + p1 − 1), (n + p1 + 1)...(n + p1 + p2 − 1), ......, (n +
p1 + p2 + ... + pm−1 + 1)...(n + p1 + p2 + ... + pm − 1) aspon teda myslim, neviem, ci som to dobre... no...
ehm... asi hej.

... pricom A ... B znamena, ze do postupnosti sa zapisu cisla A az B, ale len v pripade, ze B ≥ A.

Ak tato podmienka nie je splnena, tak sa nezapise nic (teda to funguje ako for cyklus).

Este ukazeme, ze je to skutocne bijekcia. Uvedomme si, ze oboch typov kombinacii je rovnaky pocet,

t.j.

n+k−1

k

.

Kazdu kombinaciu s opakovanim vieme zakodovat na kombinaciu bez opakovania a takisto aj opacne.

To ze vieme kazdu kombinaciu bez opakovania rozkodovat na kombinaciu s opakovanim nam vravi, ze
to kodovanie kombinacii s opakovanim na kombinacie bez opakovania je surjekcia. A teda to nutne musi
byt aj bijekcia (kvoli tomu rovnakemu poctu oboch typov kombinacii)

... Teda, neviem, ci je to celkom korektne, ale ked s tym vybehnete na pisomke, tak mam pocit, ze

vam to zhltne :)

written by shelll, shelll.host.sk

6

*******************************************************************************************

6. Zostrojte proste zobrazenie h0, 1i na (0, 1).
teda bijekciu!!!

*******************************************************************************************

|(0, 1)| ≤ |h0, 1i|
|h0, 1i| ≤ |(0, 1)|
|(0, 1)| = |h0, 1i|

Je to identita, len 0 zobrazime na

1
2 ,

1
2 na

1
4 , · · ·

1 zobrazime na

1
3 ,

1
3 na

1
9 , · · ·

0 →

1
2 ;

1

2k →

1

2k+1

k ∈ N

1 →

1
3 ;

1

3k →

1

3k+1

k ∈ N

written by shelll, shelll.host.sk

7

*******************************************************************************************

7. Nech A 6= ∅, |A| = n, nech X, Y ⊆ A, nech X ∩ Y = ∅.
Kolko je vsetkych usporiadanych dvojic (X, Y )?

*******************************************************************************************

Ukazeme, alebo je zrejme, ze mnoziny X \Y, Y \X, X ∩Y a (X ∪Y )0 su navzajom po dvoch disjunktne.

Kedze do prieniku nemozme dat ziadne prvky, mame pre kazdy prvok tri moznosti, kam ho umiest-

nime. Bud do X \ Y , alebo do Y \ X alebo do (X ∪ Y )0. A kedze ich umiestnujeme navzajom nezavisle,
tak uplatnenim pravidla sucinu dostavame pocet usporiadanych dvojic (X, Y ) rovny 3n.

P.S.: Na pisomke, ak bude cas, tak to obkecaj viac

written by shelll, shelll.host.sk

8

*******************************************************************************************

8. Nech A 6= ∅, |A| = n, nech X, Y ⊆ A, nech |(X \ Y ) ∪ (Y \ X)| = 1.
Kolko je vsetkych usporiadanych dvojic (X, Y )?

*******************************************************************************************

Vzdy musi platit X ⊂ Y a Y musi mat o jeden prvok viac a naopak.

|X| = 0 ⇒

n

0

roznych X

|Y | = 1 ⇒ n roznych Y

⇒

n

0

.n

|X| = 1 ⇒

n

1

roznych X

|Y | = 2 ⇒ (n − 1) roznych Y

⇒

n

1

.(n − 1)

|X| = 2 ⇒

n

2

roznych X

|Y | = 3 ⇒ (n − 2) roznych Y

⇒

n

2

.(n − 2)

..

.

|X| = n − 1 ⇒

n

n−1

roznych X

|Y | = n ⇒ 1 roznych Y

⇒

n

n−1

.1

teraz to treba spocitat dokopy a vynasobit dvomi (lebo to ma platit aj naopak ((X, Y ) 6= (Y, X))).

teda treba vyratat sumu:

2.

n−1

X

k=0

n

k

.(n − k)

=

2.

n−1

X

k=0

n!.(n − k)

(n − k)!.k!

=

=

2.

n−1

X

k=0

n!

(n − k − 1)!.k!

=

=

2.

n−1

X

k=0

(n − 1)!.n

(n − 1 − k)!.k!

=

=

2.n.

n−1

X

k=0

n − 1

k

=

,n−1

X

k=0

n − 1

k

= 2

n−1

=

2.n.2

n−1 =

=

n.2

n

written by shelll, shelll.host.sk

9

*******************************************************************************************

9. Dokazte, ze ak B 6= ∅, potom ani mnozina zobrazeni z A → B nie je prazdna.

*******************************************************************************************

Zobrazenie je definovane ako relacia, kde navyse plati:
1) ∀x ∈ A, ∃!y ∈ B take, ze (x, y) ∈ f (pricom f je zobrazenie f : A → B)
2) ∀x ∈ A plati : ∀y, z ∈ B plati (x, y) ∈ f ∧ (x, z) ∈ f, potom y = z

Staci ukazat, ze ak B 6= ∅, tak existuje nejake zobrazenie f : A → B.

Ak A 6= ∅, tak take mozeme najst, lebo oba vyroky 1) aj 2) su splnitelne.
Ak A = ∅, tak vyrok 1) sa stava pravdivym uz pri slovach ”∀x ∈ A”, lebo ziadne x v A nie je a vtedy sa
to chape ako splenene obdobne aj vyrok 2):
Teda aj ak A = ∅ su oba vyroky splnitelne a teda aj v tomto pripade existuje zobrazenie f : A → B.

written by shelll, shelll.host.sk

10

*******************************************************************************************

10. Dokazte, ze ak A 6= ∅ a B = ∅, tak neexistuje zobrazenie z A → B.

*******************************************************************************************

Zobrazenie je definovane ako relacia, kde navyse plati:
1) ∀x ∈ A, ∃!y ∈ B take, ze (x, y) ∈ f (pricom f je zobrazenie f : A → B)
2) ∀x ∈ A plati : ∀y, z ∈ B plati (x, y) ∈ f ∧ (x, z) ∈ f, potom y = z

Ak A 6= ∅, tak vyrok 1) skonci pri slovach ”... ∃!y ∈ B ...” lebo pre to aspon jedno x ∈ A (A 6= ∅)

neexistuje ziadne y ∈ B, nakolko v B ziadne prvky nie su. Teda neexistuje ani zobrazenie.

Pozn. Opet napis trochu viac, vies, staci obkecat, on za to da plny pocet (aspon by mal dat :)

written by shelll, shelll.host.sk

11

*******************************************************************************************

11. Dokazte, ze prazdne zobrazenie je zobrazenie, bijektivne.

*******************************************************************************************

Oba vyroky pri definicii zobrazenia (uvedene pri priklade 9.) su splnene (opat pri slovach ”∀x”)

V papieroch, co nam dali na cvikach (tych ± 20 stran) pri definicii variacii bez opakovania je taka

poznamka ze prazdne zobrazenie je injektivne, takze je aj bijektivne, lebo ked je injektiva o : ∅ → ∅,
tak aj o−1 : ∅ → ∅ je injektiva, preto je o aj surjekcia, a teda aj bijekcia. Keby nestacil argument, ze
je to v papieroch, co asi ani nebude stacit, tak to opat ukazeme z definicie injekcie, ktora znie nejako takto:

∀x, y ∈ A plati: f (x) = f (y) ⇒ x = y a opet skoncime s konstatovanim, ze vyrok je vzdy pravdivy,

nakolko A = ∅.

written by shelll, shelll.host.sk

12

*******************************************************************************************

12. Dokazte: 0! = 1.

*******************************************************************************************

Variacie n−tej triedy bez opakovania sa nazyvaju permutacie, a je ich n!. Pricom variacie bez opakova-
nia k−tej triedy su definovane ako injekcie z k−prvkovej mnoziny do n−prvkovej. A ich pocet je dany
poctom tychto injekcii. Teda pri permutaciach - su to injekcie z n−prvkovej mnoziny do n−prvkovej.
Teda pre pripad n = ∅ je to injekcia f : ∅ → ∅. A ich pocet (prudko vyuzivame predosly priklad) je teda
1, co sme mali ukazat.

V skratke: Je to injektivne zobrzenie f : ∅ → ∅ a to je len jedno, lebo prazdnu mnozinu vieme zobrazit

na praznu mnozinu prave jednym sposobom.

written by shelll, shelll.host.sk

13

*******************************************************************************************

13. Zostrojte proste zobrazenie mnoziny A na mnozinu B,
ked A = {(x, y) ∈ R × R, x2 + y2 ≤ 1}, B = h−1, 1i × h−1, 1i.
teda bijekciu!!!

*******************************************************************************************

Mnozina A je kruh (nie kruznica) s polomerom 1 a stredom v (0, 0), mnozina B je stvorec so stredom v
(0, 0) a stranou dlzky 2. Ako vyzera bijekcia. Zobrazujeme bod (x, y), pricom (x, y) ∈ A. Usecku, ktora
zacina v bode (0, 0), prechadza bodom (x, y) a konci na kruznici ohranicujucej kruh zrovnolahlime na
usecku, ktora zacina a smeruje podobne, len konci na strane stvroca (tymto ziskame rovnolahly bod s
tym povodnym). A tym bijektivne zobrazime kazdy bod tej povodnej usecky.

written by shelll, shelll.host.sk

14

*******************************************************************************************

14. Dokazte:

n
k

=

n−2
k−2

+ 2.

n−3
k−2

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

k−2
k−2

*******************************************************************************************

Najprv dokazeme LEMU: Pre n ≥ k plati:

n−k

X

i=0

n − i

k

=

n + 1

k + 1

Dokazeme matematickou indukciou podla n od k.
1

o

pre n = k:

k
k

= k+1

k+1

to plati

2

o

IP:

Pn−k

i=0

n−i

k

= n+1

k+1

n+1−k

X

i=0

n + 1 − i

k

=

n+1−k

X

i=1

n + 1 − i

k

+

n + 1

k

=

=

n−k

X

i=0

n − i

k

+

n + 1

k

=

podla IP

=

n + 1

k + 1

+

n + 1

k

=

=

n + 2

k + 1

LEMA je dokazana a teraz k zadaniu:

n − 2

k − 2

+ 2.

n − 3

k − 2

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

k − 2

k − 2

=

n−k+1

X

i=1

i.

n − 1 − i

k − 2

=

=

n−k+1

X

i=1





n−k+1

X

j=i

n − 1 − j

k − 2





=

=

n−k+1

X

i=1





n−i−k+1

X

j=0

n − 1 − i − j

k − 2





=

podla LEM Y

=

n−k+1

X

i=1

n − i

k − 1

=

=

n−k

X

i=0

n − i − 1

k − 1

=

podla LEM Y

=

n

k

written by shelll, shelll.host.sk

15

*******************************************************************************************

15. Dokazte:

k

X

r=0

n

r

.

m

k − r

=

m + n

k

*******************************************************************************************

To je von der Mondova konvolucia.
Kombinatorickou uvahou (to je korektny dokaz). To na pravej strane nam hovori, ze vyberame k prvkov
z m + n prvkovej mnoziny, to vieme spravit

m+n

k

moznymi sposobmi.

To vlavo nam hovori to iste, akurat ich vyberame trosku inym sposobom. Rozdelime si mnozinu na dve
disjunktne (je jedno ako), pricom prva, oznacme N , bude mat n prvkov a druha, oznacme M , m prvkov.
A teraz postupne... z N nevyberieme nic, z M k prvkov, to je

n

0

. m

k

sposobmi, potom mozeme z N

zobrat 1, z M k − 1 prvkov, atd. teda suma cez vsetky 0 ≤ r ≤ k

n

r

. m

k−r

. Oba sposoby vyberu

su navzajom ekvivalentne (oba popisuju vsetky moznosti kombinacii k−tej triedy z m + n prvkovej
mnoziny), tym je rovnost dokazana.

written by shelll, shelll.host.sk

16

*******************************************************************************************

16. Dokazte:

4.

X

k

n

4k

= 2

n + 2

n

2 +1

. cos

n.π

4

*******************************************************************************************

Ked si rozpises sucet (1 + 1)n + (1 − 1)n + (1 + i)n + (1 − i)n pomocou binomickych viet, tak by
ti mali ostat len cleny tak ako su popisane na lavej strane dokazovanej rovnice (ostatne sa vyskrtaju,
ostanu len cleny typu

n

4k

a kzdy z nich styri krat).

A tiez:

(1 + 1)

n + (1 − 1)n + (1 + i)n + (1 − i)n =

=

2

n + 0n +

√

2.

cos

π

4

+ i. sin

π

4

n

+

√

2.

cos

π

4

− i. sin

π

4

n

=

(podla moivrovej vety)

=

2

n +

√

2

n

.

cos

n.π

4

+ i. sin

n.π

4

+

√

2

n

.

cos

n.π

4

− i. sin

n.π

4

=

roznasobime zatvorky

=

2

n + 2.

√

2

n

. cos

n.π

4

=

=

2

n + 2

n

2 +1

. cos

n.π

4

co bolo treba ukazat.

written by shelll, shelll.host.sk

17

*******************************************************************************************

17. Najdite minimalnu hodnotu suctu:

s

X

i=1

ni

k

pricom : n = n1 + n2 + ... + ns

*******************************************************************************************

Ukazeme, ze pre k > 1 plati

n+1

k

+

n−1

k

> 2.

n
k

Lavu stranu rozpiseme ako:

n

k

+

n

k − 1

+

n − 1

k

+

n − 1

k − 1

−

n − 1

k − 1

=

=

n

k

+

n

k − 1

+

n

k

+

n − 1

k − 1

>

>

ma byt > 2.

n

k

upravou nerovnice

n

k−1

>

n−1
k−1

co po rozpisani a skrtani dostaneme n > n − k + 1 teda k > 1, co je

pravda, obratime postup a je to.

Teraz si vsimneme, ze pokial pre vsetky i 6= j plati, ze |ni − nj| ≤ 1, bude suma minimalna, lebo

uz nebude co zlepsovat. Dostavame takto (n mod s) .

n div s+1

k

+ (n − n mod s) .

n div s

k

co je

minimalna hodnota danej sumy

written by shelll, shelll.host.sk

18

*******************************************************************************************

18. Dokazte binomicku vetu.

*******************************************************************************************

Matematickou indukciou.
1

o

1 = (x + y)

0 =

0

0

.x

0.y0 = 1

2

o

IP: (x + y)

n = Pn

k=0

n
k

.xk.yn−k

(x + y)

n+1

=

(x + y).(x + y)

n =

podla IP

=

(x + y)

n.

n

X

k=0

n

k

.x

k .yn−k =

=

x.

X

+y.

X

=

=

n

X

k=0

n

k

.x

k+1.yn−k +

n

X

k=0

n

k

.x

k .yn − k + 1 =

=

n+1

X

k=1

n

k − 1

.x

k .yn−k+1 +

n

X

k=0

n

k

.x

k .yn − k + 1 =

=

n

n

.xn + 1 +

n

X

k=1

n

k − 1

.x

k .yn − k + 1 +

n

X

k=1

n

k

.x

k .yn−k+1 +

n

0

.y

n+1 =

=

n + 1

n + 1

.xn + 1 +

n

X

k=1

n

k − 1

.x

k .yn − k + 1 +

n

k

.x

k .yn−k+1

+

n

0

.y

n+1 =

=

n + 1

n + 1

.xn + 1 +

n

X

k=1

n + 1

k

.x

k .yn − k + 1 +

n

0

.y

n+1 =

=

n+1

X

k=0

.x

k .yn−k+1

written by shelll, shelll.host.sk

19

*******************************************************************************************

19. Mame zoradit 2n Anglicanov, 2n + 1 Francuzov a 2(n + 2) Talianov do radu tak, ze kazdy
A bude stat medzi F a T a ziadny F nebude stat vedla T .
Kolkymi sposobmi sa to da spravit?

*******************************************************************************************

Najskor ich berieme ako farebne (neocislovane) gulicky.
Dolezite je uvedomit si, ze dvaja anglicania nemozu byt vedla seba. Takto nam medzi nimi vznikne
2n − 1 medzier, a kedze A musi byt medzi F a T , musime dat dakoho este po krajoch. Dalej si musime
uvedomit, ze kazdu medzeru medzi anglicanmi + 2 kraje mozeme vyplnit len ludmi jednej narodnosti.
A kedze A musi byt medzi F a T , tak sa nam tieto skupiny budu striedat. Dostavame dve moznosti
(este ze je A parny pocet), ktore vyzeraju dajako takto:

[F..F ]A[T..T ]A[F..F ]A ... A[T..T ]A[F..F ]

>

n + 1 skupin F a n skupin T

[T..T ]A[F..F ]A[T..T ]A ... A[F..F ]A[T..T ]

>

n + 1 skupin T a n skupin F

Dalej vieme, ze jednak do tych skupin musime rozhodit vsetkych F , resp. T , a za druhe, ze ich

mozeme rozhadzovat nezavisle od seba (teda F nezavisle od T ).

Pocet moznosti, ako rozhodit n guliciek do k skupin = pocet kladnych celocislenych rieseni sustavy

a1 + a2 + ... + ak = n t.j.

n−1
k−1

Teda:
pocet rozhodeni 2n + 1 F do n + 1 skupin:

2n

n

pocet rozhodeni 2n + 4 T do n skupin:

2n+3

n−1

pocet rozhodeni 2n + 4 T do n + 1 skupin:

2n+3

n

pocet rozhodeni 2n + 1 F do n skupin:

2n

n−1

Spolu to mame (pre gulicky, nie pre konkretnych ludi):
P’ =

2n

n

. 2n+3

n−1

+

2n

n−1

. 2n+3

n

No a ked tych ludi berieme nie ako gulicky, ale ako individuality, tak pre kazde zoradenie mozeme

nezavisle na sebe poprehadzovat konkretnych A, F , a T , teda pre jedno rozostavenie mame (2n)!.(2n +
1)!.(2n + 4)!, spolu teda

P = (2n)!.(2n + 1)!.(2n + 4)!.P’ = (2n)!.(2n + 1)!.(2n + 4)!.

h

2n

n

. 2n+3

n−1

+

2n

n−1

. 2n+3

n

i

written by shelll, shelll.host.sk

20

*******************************************************************************************

20. Nech A je podmnozina B(n, l) a B mnozina vsetkych vektorov z B(n, k) porovnatelnych
aspon s jednym vektorm v A.
Dokazte, ze

|A|

(

n

l )

≤

|B|

(

n
k)

B(n, i) obsahuje tie vektory z {0, 1}n, ktore obsahuju prave i jednotiek; ak a = (a1, . . . , an),
b = (b1, . . . , bn), tak a ≤ b, ak ai ≤ bi, pre vsetky i;
a, b su porovnatelne, ak a ≤ b a b ≤ a.

*******************************************************************************************

Najprv si vsimnime, ze |B(n, l)| =

n

l

, lebo obsahuje vsetky n prvkove binarne vektory (zlozene z 0 a

1), ktore maju prave l jedniciek.
Teda |A| ≤ |B(n, l)|
Dalej si ukazeme, ze B = B(n, k).
Nech k > l Potom vezmime nejaky vektor α ∈ B(n, k), ten obsahuje k 1dniciek. Vytvrome novy vektor
β. Z tychto k jedniciek vieme vybrat l jedniciek. Tie ponechame, ostatne zmenime na 0. Potom tento
vektor β je z B(n, l) a plati, ze α > β
Podobne to bude pri k = l (tam bude nostra nerovnost) a pri k < l (tam β > α)

Teda ku kazdemu vektoru α ∈ B(n, k) vieme najst vektor β ∈ B(n, l), s ktorym je porovnatelny, a

teda B = B(n, k), a tiez |B| = |B(n, k)| =

n
k

.

Upravujme nasu nerovnost:

|A|

(

n

l )

≤

|B|

(

n
k)

= 1

|A| ≤

n

l

, co plati, nakolko A je podmnozina B.

Obratenim postupu sme dokazali nasu nerovnost.

written by shelll, shelll.host.sk

21

*******************************************************************************************

21.

a) kolkymi sposobmi mozeme rozdelit n roznych predmetov medzi k ludi?

b) to iste, len kazda osoba musi dostat minimalne r predmetov. (0 < r a k.r < n)

*******************************************************************************************

a) Je to ekvivalentne poctu kladnych celociselnych rieseni rovnice x1 + x2 + · · · + xk = n, co je

n−1
k−1

dokaz je v papieroch pri ratani poctu kombinacii.

b) Je to ekvivalentne poctu celociselnych rieseni rovnice x1 + x2 + · · · + xk = n, ale pricom este xi ≥ r.

Upravime na (x1 − (r − 1)) + (x2 − (r − 1)) + · · · + (xk − (r − 1)) = n − k.(r − 1), co pri oznaceni
x0

i = (xi − (r − 1)) ≥ 1 dava rovnicu x

0

1 + x

0

2 + · · · + x

0
k = n − k(r − 1) a pocet rieseni kladnych

celociselnych tejto rovnice

n−1−k.(r−1)

k−1

written by shelll, shelll.host.sk

22

*******************************************************************************************

22. T (n) - pocet postupnosti z 0 a 1 dlzky n takych, ze ziadne dve 1 nestoja vedla seba.
Dokazte: T (n) = T (n − 1) + T (n − 2)
Vyjadrite T (n) pomocou kombinacnych cisiel.

*******************************************************************************************

Majme postupnost n samych nul. Vyberme z tych nul prave k, ktore potom zmenime na 1, pricom
nesmieme vybrat dve vedlajsie nuly. To vieme spravit

n+1−k

k

sposobmi.

Preco? Vyberme nejaku nulu. Nulu vpravo od nej vylucime. Co ked vyberieme uplne najsampravsiu

nulu? Musime si jednu nulu pridat. Teraz vieme, ze mame n+1 nul, pricom z prvych n nejako vyberieme
k nul tak, ze ziadne dve vybrane nebudu vedla seba. Tie vzdy vpravo od nich vylucime. Teraz ostane
n + 1 − k nul, z ktorych mame vybrat lubovolnych k.

Tak a teraz uz vieme vyjadrit T (n). To je T (n) =

P k

n+1−k

k

, pricom berieme vsetky rozumne k, teda

k ≥ 0 a zaroven n + 1 − k ≥ k, teda k ≤

n+1

2

teda T (n) =

[

n+1

2

]

P

k=0

n+1−k

k

este treba to T (n) = T (n − 1) + T (n − 2)

T (n − 1) + T (n − 2)

=

[ n

2 ]

X

k=0

n − k

k

+

[

n−1

2

]

X

k=0

n − 1 − k

k

=

=

[ n

2 ]

X

k=0

n − k

k

+

[

n−1

2

+1

]

X

k=1

n − k

k − 1

=

=

n

k

+

[

n−1

2

+1

]

X

k=1

n − k

k

+

n − k

k − 1

=

=

n

k

+

[

n−1

2

+1

]

X

k=1

n − k + 1

k

=

=

[

n−1

2

+1

]

X

k=0

n − k + 1

k

=

=

[

n+1

2

]

X

k=0

n + 1 − k

k

= T (n)

Este sa tam treba pohrat s paritou n . . .

written by shelll, shelll.host.sk

23

*******************************************************************************************

23. Dokazte:

n

X

k=1

1

(k − 1)! · k!

·

1

((n − k)!)2

=

(2n − 1)!

(n! · (n − 1)!)2

*******************************************************************************************

n

X

k=1

1

(k − 1)! · k!

·

1

((n − k)!)2

=

(2n − 1)!

(n! · (n − 1)!)2

/·n!

n

X

k=1

n!

(n − k)! · k!

·

1

(n − k)! · (k − 1)!

=

(2n − 1)!

n! · ((n − 1)!)2

n

X

k=1

n

k

·

1

(n − k)! · (k − 1)!

=

(2n − 1)!

n! · ((n − 1)!)2

/·(n − 1)!

n

X

k=1

n

k

·

(n − 1)!

(n − k)! · (k − 1)!

=

(2n − 1)!

n! · (n − 1)!

n

X

k=1

n

k

·

n − 1

k − 1

=

(2n − 1)!

n! · (n − 1)!

n

X

k=1

n

k

·

n − 1

k − 1

=

2n − 1

n

→ to plati, van der Mondova konvolucia

obratime postup a je to.

written by shelll, shelll.host.sk

24

*******************************************************************************************

24. Aky bude najvacsi koeficient vo vyraze:

a) (a + b + c)10

b) (a + b + c + d)14

*******************************************************************************************

Budeme vychadzat z polynomickej vety.

a) z polynomickej vety vyplyva: (a + b + c)10 =

P

10!

k1!·k2!·k3!

· (ak1 + bk2 + ck3 ),

k1 + k2 + k3 = 10

staci uz len najst najvacsi zlomok zo sumy, teda k1! · k2! · k3! musi byt najmensie, v tomto pripade
to je: k1 = 3, k2 = 3, k3 = 4

10!

3!·3!·4! = 4200 co je vysledok

b) z polynomickej vety vyplyva: (a + b + c + d)14 =

P

14!

k1!·k2!·k3!·k4!

· (ak1 + bk2 + ck3 + dk4 ),

k1 +

k2 + k3 + k4 = 14
staci uz len najst najvacsi zlomok zo sumy, teda k1! · k2! · k3! · k4! musi byt najmensie, v tomto
pripade to je: k1 = 3, k2 = 3, k3 = 3, k4 = 5

14!

3!·3!·3!·5! = 4204200 co je vysledok

na skuske tam napiste viac, hlavne tam, kde hladate ten najvacsi zlomok . . .

written by shelll, shelll.host.sk

25

*******************************************************************************************

25. Dokazte:

n

X

k=0

(−1)

k ·

1

k + 1

·

n

k

=

1

n + 1

*******************************************************************************************

dokazem to priamo:

n

X

k=0

(−1)

k ·

1

k + 1

·

n

k

=

n

X

k=0

(−1)k · n!

(k + 1)! · (n − k)!

=

=

n

X

k=0

(−1)k · (n + 1)!

(n + 1) · (k + 1)! · (n − k)!

=

=

1

n + 1

·

n

X

k=0

(−1)

k

n + 1

k + 1

=

=

1

n + 1

·







n + 1

1

−

n + 1

2

+ · · · + (−1)

n ·

n + 1

n + 1

−

n + 1

0

|

{z

}

=0

+

n + 1

0







=

=

1

n + 1

·

0 +

n + 1

0

=

=

1

n + 1

· (0 + 1) =

=

1

n + 1

written by shelll, shelll.host.sk

26

*******************************************************************************************

26. Dokazte:

n

X

k=1

(−1)

k−1 ·

1

k

·

n

k

= 1 +

1

2

+

1

3

+ · · · +

1

n

*******************************************************************************************

dokazem to MI:
1

o

pre 1 (pre 0 nie, lebo ta suma ide od 1): 1 = 1

2

o

IP:

n

P

k=1

(−1)k−1 ·

1
k ·

n
k

= 1

2 +

1
3 + · · · +

1

n

ma platit

n+1

P

k=1

(−1)k−1 ·

1
k ·

n+1

k

= 1 + 1

2 +

1
3 + · · · +

1

n+1

1 +

1

2

+

1

3

+ · · · +

1

n + 1

=

1 +

1

2

+

1

3

+ · · · +

1

n

+

1

n + 1

=

z IP a predoslej (25.) ulohy

=

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

+

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

co sme mali dokazat

written by shelll, shelll.host.sk

27

*******************************************************************************************

27. Mame n Anglicanov a m Francuzov. Kolkymi sposobmi ich mozme rozostavit, aky
nebol ziaden Anglican ani ziaden Francuz osamoteny - tj.

stoji vedla neho este jeden

sukmenovec?

*******************************************************************************************

Najprv ich budeme brat ako farebne gulicky.

Kolkymi sposobmi rozdelime A na k skupin tak, aby v kazdej boli aspon dvaja? To je ekvivalentne s

rovnicou a1 + · · · + ak = n ∧ ∀i; ai ≥ 2, co je zase ekvivalentne s a

0

i + · · · + a

0

k = n − k ∧ ∀i; a

0

i = ai − 1 ≥ 1

o ktorej vieme, ze ma

n−k−1

k−1

rieseni. A ako medzi nich narvat m F? Ti musia byt v kazdej medzere,

teda ich skupin musi byt aspon k − 1, ale zaroven ich moze byt najviac n + 1, lebo uz mozu pribudnut len
dve skupiny - na zaciatku a na konci. Ak mame k − 1 skupin F, na to mame analogicky

m−k

k−2

moznosti

a je jasne, ako ich tam postavime. Podobne ak je F k + 1 skupin, na to mame

m−k−2

k

moznosti a

opat je jedina moznost, ako ich tam postavit. Ak ich je k skupin, moznosti je

m−k−1

k−1

, a postavit ich

tam mozeme dvomi sposobmi - bud je jedna skupina na zaciatku, alebo je jedna na konci. Dokopy to
pre kazde rozostavenie k skupin A dava

m−k

k−2

+ 2 · m−k−1

k−1

+ m−k−2

k

vyhovujucich rozostaveni. No a

hladany pocet by bol potom sucet tohto cez vsetky 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 este stale vizera divne koli tej sume do ∞ a este sme nezaratali rozlisitelnost ludi. Ked

ale mame nejake usporiadanie, kde mame povedane, kde stoja A a kde F, tak konkretnych ludi nan
mozemepostavit n! · m! sposobmi. No a z tej sumy je nenulovych len prvych b

n

2 c clenov, lebo pre k > b

n

2 c

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

n−k−1

k−1

= 0, cize aj cely scitanec je 0. Vysledok ulohy je teda:

n! · m! ·

b n

2 c

X

k=1

n − k − 1

k − 1

·

m − k

k − 2

+ 2 ·

m − k − 1

k − 1

+

m − k − 2

k