1 M ATEMATI ČKA INDUKCIJA - I DEO

Zadatak 1.1. Ako je a1 = 1, a2 = 2 i an = (n − 1)( an−1 + an−2 ) za n ≥ 3, tada je

za sve prirodne brojeve n ∈ N ispunjeno an = n!.

Zadatak 1.2. Dokazati da je za svaki prirodan broj n ≥ 2 važi

n puta
z
r }| {
q √
2− 2+ 2+···+ 1 2
r > .
q √ 4
2− 2+ 2+···+ 2
| {z }
n−1 puta

Zadatak 1.3. Iz table formata 2n × 2n izbačeno je jedno jedinično polje. Dokazati

da se ostatak table može popločati koristeći figuricu (dozvoljeno je rotirati

figuricu).

Zadatak 1.4. Dokazati da je svaki prirodan broj veći od 1 ili prost ili proizvod
prostih brojeva.

Zadatak 1.5. Dokazati da je svaki prirodan broj zbir različitih stepena dvojke.

Zadatak 1.6. Na stolu je nekoliko bokala sa vodom, tako da je u svim bokalima

ukupno 22019 litara vode, a zapremina svakog bokala veća je od 22019 litara.
Ukoliko bokal A sadrži barem onoliko litara vode koliko i bokal B, može se u
jednom potezu prebaciti iz bokala A u bokal B onoliko vode koliko je već u
bokalu B. Dokazati da se sa nekoliko poteza sva voda može presipati u jedan
bokal, bez obzira na početni raspored vode po bokalima.

Zadatak 1.7. U nekoj državi izmedju svaka dva grada postoji jednosmerna au-
tobuska linija. Dokazati da u toj državi postoji grad iz kog se u svaki drugi grad
može stići sa najviše jednim presedanjem.

Zadatak 1.8. Dokazati da za svaki prirodan broj n ∈ N važi nejednakost

1 1 1 3
1+ 3
+ 3 +···+ 3 < .
2 3 n 2
2 M ATEMATI ČKA INDUKCIJA - II DEO
Zadatak 2.1. Dokazati da za svaki prirodan broj m postoji prirodan broj k tako
da važi
m = ±12 ± 22 ± · · · ± k2
za pogodan izbor znakova + i −.

Zadatak 2.2. Neka su a1 , a2 , . . . , an nenegativni realni brojevi. Dokazati da važi

nejednakost
a1 + a2 + · · · + a n √
≥ n a1 · a2 · . . . · a n .
n
Zadatak 2.3. Koliko ima 2019-tocifrenih brojeva, koji se pišu samo pomoću ci-
fara 1, 2, 3 i u kojima se cifra 1 javlja paran broj puta?

Zadatak 2.4. 2019 revolveraša stoje na ravnoj livadi. Rastojanja medju revolverašima
su medjusobno različita. Svaki revolveraš, tačno u podne, poteže i puca u onog
koji mu je najbliži. Dokazati da postoji revolveraš u kog niko neće da puca.

Zadatak 2.5. Dokazati da se svaka mreža od n ≥ 5 gradova može povezati

jednosmernim autobuskim linijama, takvim da se iz svakog grada može stići u
svaki drugi sa najviše jednim presedanjem.

Zadatak 2.6. Temena konveksnog poligona su obojena sa najmanje tri različite

boje tako da ne postoje dva susedna temena obojena istom bojom. Dokazati da
se može izvršiti triangulacija poligona dijagonalama koje se ne seku i čiji krajevi
su obojeni različitim bojama.

Zadatak 2.7. Neka su a1 , a2 , . . . , an različiti neparni prirodni brojevi, takvi da

su njihove razlike različite. Dokazati da suma a1 + a2 + · · · + an nije manja od
n ( n2 + 2)
.
3
3 D IRIHLEOV PRINCIP
Zadatak 3.1. Ako je m objekata rasporedjeno u n kutija i m > kn, tada se u bar
jednoj kutiji nalazi bar k + 1 objekata.

Zadatak 3.2. Bela ravan je na proizvoljan način poprskana plavom bojom. Dokazati
da u toj plavo-beloj ravni postoje dve tačke iste boje na rastojanju 2019.

Zadatak 3.3. U krug poluprečnika 1 uočeno √ je 5 tačaka. Dokazati da medju

njima postoje 2 čije rastojanje nije veće od 2.

Zadatak 3.4. Unutar kvadrata dužine stranice 1 date su 33 tačke, od kojih nikoje
tri nisu kolinearne. Dokazati da u datom skupu tačaka postoje 3, tako da obim
trougla koji odredjuju nije veći od 1.

Zadatak 3.5. Koliko najviše kraljeva možemo postaviti na šahovsku tablu tako
da se nikoja dva od njih ne tuku?

Zadatak 3.6. Neka je X skup od n osoba. Dokazati da postoje bar dve osobe iz X
koje imaju isti broj poznanika u X. (Pretpostavlja se da je poznanstvo simetrična
relacija.)

Zadatak 3.7. (a) Dokazati da u proizvoljnom skupu od n + 1 prirodnih brojeva

postoje dva čija je razlika deljiva sa n.

(b) Dokazati da za svaki prirodan broj n postoji broj oblika 11 . . . 100 . . . 0 koji je
deljiv sa n.

Zadatak 3.8. Dokazati da se medu n + 1 različitih prirodnih brojeva manjih od

2n mogu naći tri broja tako da jedan od njih bude jednak zbiru ostala dva.

Zadatak 3.9. Neka je A = { a1 , a2 , a3 , a4 , a5 } skup od 5 prirodnih brojeva. Dokazati

da je za proizvoljnu permutaciju ai1 ai2 ai3 ai4 ai5 skupa A proizvod

( ai1 − a1 )( ai2 − a2 ) · · · ( ai5 − a5 )

uvek paran.

Zadatak 3.10. Neka je r ∈ R proizvoljan realan broj. Dokazati da medju broje-

vima r, 2r, . . . , 99r postoji najmanje jedan koji se razlikuje od nekog celog broja
1
za ne više od 100 .
4 K OMBINATORIKA - I DEO
Zadatak 4.1. Na koliko načina elemente skupa A = { a1 , a2 , . . . , an } možemo
poredjati u niz dužine k ako

(a) elementi niza ne moraju biti različiti?

(b) elementi niza moraju biti medjusobno različiti?

Zadatak 4.2. Na koliko načina sve elemente skupa A = { a1 , a2 , . . . , an } možemo

poredjati u niz (bez ponavljanja)?

Zadatak 4.3. Neka je dat skup A = { a1 , a2 , . . . , an } i k ≤ n. Koliko k-elementnih

podskupova sadrži skup A?

Zadatak 4.4. Na koliko načina od 2 matematičara i 8 ekonomista možemo formi-

rati petočlanu komisiju u kojoj će biti bar jedan matematičar?

Zadatak 4.5. Koliko se petocifrenih brojeva, sa različitim ciframa, može sastaviti

od cifara 0, 1, 2, 3, 4?

Zadatak 4.6. Koliko delilaca ima prirodan broj n čija je kanonska faktorizacija
α
p1α1 p2α2 · · · pk k ?

Zadatak 4.7. U ravni je dato n tačaka. Koliko je pravih odredjeno tim tačkama
ako:

(a) nikoje tri nisu kolinearne?

(b) m tačaka pripadaju jednoj pravoj, a medju ostalim n − m tačaka nikoje tri
nisu kolinearne i nikoje dve nisu kolinearne sa nekom od prvih m tačaka?

Zadatak 4.8. Neka su m i n prirodni brojevi. Označimo sa S0 skup svih (m +

n)- varijacija elemenata 0 i 1, koje sadrže m nula i n jedinica. Neka je S1 skup
svih onih varijacija iz S0 u kojima nikoje dve nule nisu susedne, a S2 skup onih
varijacija iz S1 čiji prvi i poslednji član nisu jednaki 1. Odrediti |S0 |, |S1 |, |S2 |.

Zadatak 4.9. Dato je 10 belih i 10 crnih kuglica koje su označene brojevima od 1

do 10. Na koliko načina je moguće izabrati 6 kuglica, tako da medju izabranim
kuglicama

(a) nema kuglica označenih istim brojem?

(b) ima tačno 2 para kuglica označenih istim brojem?

5 K OMBINATORIKA - II DEO
Zadatak 5.1. Na koliko načina možemo smestiti 6 osoba oko okruglog stola ako:

(a) sve stolice su jednake i nijedno mesto nije posebno istaknuto?

(b) sve stolice su medjusobno različite?

Zadatak 5.2. Koliko permutacija ( a1 , a2 , . . . , a2019 ) skupa {1, 2, . . . , 2019} zado-

voljava da 3| ai − i za svako i = 1, 2019?

Zadatak 5.3. Iz kompleta koji sadrži 4 karte, koje su numerisane brojevima 1, 2,

3 , 4, bira se sa vraćanjem 10 karata. Na koliko načina se mogu izabrati jedna
jedinica, dve dvojke, tri trojke i četiri četvorke?

Zadatak 5.4. Na koliko načina k identičnih kuglica možemo rasporediti u n ra-

zličitih kutija?

Zadatak 5.5. Koliko se različitih nizova ( a1 , a2 , . . . , ak ) može napraviti od bro-

jeva {1, 2, . . . , n} ako su nizovi takvi da važi:

(a) a1 ≤ a2 ≤ . . . ≤ ak ?

(b) a1 < a2 < . . . < ak ?

Zadatak 5.6. U pekari pored škole prodaju se pogačice, kifle, djevreci i krofne
i samo je jedna radnica za kasom. Za vreme velikog odmora, 50 učenika je
svratilo u pekaru i svako je kupio po jedan komad peciva. Na koliko različitih
načina su ove kupovine mogle da se odvijaju ako:

(a) važno je koji je učenik kupio koji komad peciva, ali redosled kupovine nije
bitan?

(b) važno je koji je učenik kupio koji komad peciva i koji je po redu bio pri
kupovini?

(c) nije važno koji je učenik kupio koji komad peciva niti redosled učenika pri
kupovini?

(d) nije važno koji je učenik kupio koji komad peciva niti redosled učenika pri
kupovini, ali se zna da je kupljeno barem jedno pecivo od svake vrste?

Zadatak 5.7. Iz kompleta koji sadrži 32 različite karte vrši se izbor 8 karata: a)
sa vraćanjem; b) bez vraćanja. Odrediti broj različitih izbora, ako: 1) redosled
izbora jeste bitan; 2) redosled izbora nije bitan.
6 B INOMNA I POLINOMNA FORMULA
Zadatak 6.1. Dokazati da za svaki prirodan n važi
           
n n n n n n
+ + +... = + + +....
0 2 4 1 3 5

Zadatak 6.2. Dokazati naredne identitete:

(a) ∑nk=0 k · (nk) = n · 2n−1 ;

2
(b) ∑nk=0 (nk) = (2n
n );

(c) ∑nk=r (r+r k) = (nr+

+1
1 ).

Zadatak 6.3. Dokazati da je:

√ √
(a) broj (2 + 17)n + (2 − 17)n prirodan;
√
(b) broj [(2 + 3)n ] neparan.

Zadatak 6.4. Dokazati da je za svaki prirodan broj n

       
n n n n −1 n
−2 +3 + · · · + (−1) n = 0.
1 2 3 n

Zadatak 6.5. Dokazati da je za svaki prirodan broj n

2n +1 − 1
       
1 n 1 n 1 n 1 n
1+ + +···+ + = .
2 1 3 2 n n−1 n+1 n n+1

Zadatak 6.6. Naći koeficijent uz x13 x23 x3 x42 u razvoju izraza

( x1 − x2 + 2x3 − 2x4 )9 .
7 F ORMULA UKLJU ČIVANJA I ISKLJU ČIVANJA
Zadatak 7.1. Neka su A1 , A2 i A3 konačni skupovi. Dokazati da je

(a) | A1 ∪ A2 | = | A1 | + | A2 | − | A1 ∩ A2 |;

(b) | A1 ∪ A2 ∪ A3 | = | A1 | + | A2 | + | A3 | − | A1 ∩ A2 | − | A2 ∩ A3 | − | A3 ∩ A1 | +
| A1 ∩ A2 ∩ A3 |.
Zadatak 7.2. U razredu ima 30 učenika. Pri tome, odličnu ocenu iz matematike
ima 15 učenika, iz fizike 13 učenika, iz hemije 12 učenika, iz matematike i fizike
8 učenika, iz fizike i hemije 6 učenika, iz hemije i matematike 7 učenika, a iz
sva tri predmeta 3 učenika. Koliko učenika ima bar jednu odličnu ocenu iz
navedenih predmeta?

Zadatak 7.3. Koliko ima prirodnih brojeva manjih ili jednakih 1000 koji nisu
deljivi ni sa 2 ni sa 3 ni sa 5?

Zadatak 7.4. Koliko ima permutacija slova

M, A, T, H, I, S, F, U, N,

tako da se u njima ne pojavljuju reči MATH, IS, FUN kao uzastopna slova?

Zadatak 7.5. Neka su A1 , A2 , . . . , An podskupovi konačnog skupa S i neka važe

sledeće jednakosti:

|S| = M, |S \ ( A1 ∪ A2 ∪ · · · ∪ An )| = M0 ,
| Ai | = M1 , i ∈ {1, 2, . . . , n},
| Ai ∩ A j | = M2 , i, j ∈ {1, 2, . . . , n}, i 6= j,
..
.
| A1 ∩ A2 ∩ · · · ∩ A n | = Mn .

Tada je
     
n n ( n −1) n
| A1 ∪ A2 ∪ · · · ∪ An | = nM1 − M2 + M3 − · · · + (−1) Mn .
2 3 n

Zadatak 7.6. Neka je S = {1, 2, . . . , n}, F = { f | f : S → S} i F0 ⊂ F skup onih

funkcija f : S → S koje nemaju nepokretnih tačaka. Odrediti broj elemenata
skupa F0 .
8 K OMPLEKSNI BROJEVI
9 N IZOVI
√
Zadatak 9.1. Niz { xn }n∈N definisan je sa xn+1 = 3− 1
xn , n ∈ N i x1 = 1.
Odrediti x2020 .
Rešenje. Jednostavnim računom dobijamo da je
√
x2 = 3 − 1,
√ √
√ 1 3 3+1 3−1
x3 = 3 − √ = = ,
3−1 − 2 2
√
√ 2 √ 2 3+2
x4 = 3 − √ = 3− = −1,
3−1 2
√
x5 = 3 + 1,
√ √
√ 1 √ 3−1 3+1
x6 = 3 − √ = 3− = ,
3+1 2 2
√
√ 2 √ 2 3−2
x7 = 3 − √ = 3− = 1.
3+1 2
Kako je x1 = x7 , zaključujemo da je xn = xn+6 za svako n ∈ N. Iz 2020 =
336 · 6 + 4, sledi da je x2020 = x4 = −1. 
Zadatak 9.2. Niz { an }n∈Z sastavljen je od prirodnih brojeva i ispunjava uslov
a +a
an = n−1 2 n+1 za svako n ∈ Z. Dokazati da je ovaj niz konstantan.
Rešenje. Pretpostavimo da niz nije konstantan i neka je a1 = a. Tada postoji
l ∈ Z takav da je al 6= a1 . Razlikovaćemo dva slučaja: kada je l > 1 i kada je
l ≤ 0.
Pretpostavimo najpre da je l > 1 i neka je l0 = min{l ∈ N : al 6= a1 }. U slučaju
da je l0 ≥ 3 imamo da je a1 = a2 = · · · = al0 −2 = al0 −1 = a i al0 6= a. Medjutim,
a l −2 + a l a+ al
iz al0 −1 = 0 2 0 imamo da je a = 2 0 , pa sledi da je al0 = a. Dakle, mora biti
l0 = 2. Neka je a2 = b > a. Slučaj kada je a > b se radi analogno. Iz a1 = a0 +2 a2
sledi da je a0 = 2a − b. Na isti način dobijamo da je a−1 = 3a − 2b, a−2 = 4a − 3b
i
a−k = (2 + k ) a − (1 + k)b = (2a − b) − k (b − a), k ∈ N.
Kako je b − a > 0, sledi da je za dovoljno veliko k član a−k negativan, što je u
suprotnosti sa tim da su svi članovi niza prirodni brojevi. Prema tome, niz mora
biti konstantan.
Slučaj kada je l ≤ 0 se razmatra analogno. 
1
Zadatak 9.3. Niz { an }n∈N definisan je sa a1 = 1 i an+1 = an + an za svaki
prirodan broj n. Dokazati da je 14 < a100 < 18.
Rešenje. Primetimo da je a2n+1 = ( an + 1/an )2 = a2n + 1/a2n + 2. Zbog toga je
a2n + a23 + . . . + a2100 = ( a21 + 1/a21 + 2) + ( a22 + 1/a22 + 2) + . . . + ( a299 + 1/a299 + 2).
Potiranjem istih veličina s leve i desne strane, i imajući u vidu da je a1 = 1,
zaključujemo:
1 1 1
a2100 = 200 + 2 + 2 + . . . + 2 .
a2 a3 a99
Broj sa desne strane je veći od 196 = 142 , pa je a100 > 14. Takodje, kako je
a2 , a3 , . . . > 1, broj sa desne strane je manji od 324 = 182 , pa je a100 < 18.

Zadatak 9.4. Neka je { an }n∈N strogo rastući niz prirodnih brojeva, pri čemu je
a1 = 1 i a2 = 2. Ako za svaka dva uzajamno prosta prirodna broja k i l važi
akl = ak al , dokazati da je onda an = n za svaki prirodan broj n.
Rešenje. Dokažimo najpre da je a3 = 3. Neka je a3 = a. Pošto je niz strogo
rastući, imamo a15 = a · a5 < a18 = 2 · a9 , ali a9 < a10 = 2 · a5 pa je zato
a15 = a · a5 < 2 · 2 · a5 = 4 · a5 . Prema tome, a3 < 4 pa je a3 = 3.
Dokažimo sada, transfinitnom indukcijom, da je an = n za svako n. Za n =
1, 2, 3 to važi. Neka je ak = k za svako k = 1, 2, . . . , n, n > 3 i dokažimo da
važi i za k = n + 1. Pošto su brojevi n i n − 1 uzajamno prosti, sledi da je
an(n−1) = an an−1 = n(n − 1). Za n ≥ 3, važi i n(n − 1) > n + 1 jer je ta
nejednakost ekvivalentna sa (n − 1)2 − 2 > 0, što je tačno za svako n ≥ 3.
Dakle, a1 = 1, an(n−1) = n(n − 1), a broj n + 1 je izmedju 1 i n(n − 1). Pošto je
niz strogo rastući, sledi da mora biti an+1 = n + 1.

Zadatak 9.5. Odrediti opšti član niza

1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, . . .

u funkciji od njegovog indeksa u nizu.

Rešenje. Neka je m ∈ N. Uočimo da je am = n ako i samo ako važi

( n − 1) n n ( n + 1)
<m≤ ,
2 2
tj.,
n2 − n n2 + n
+1 ≤ m ≤ .
2 2
Ova nejednakost je ekvivalentna sa

n2 − n + 2 ≤ 2m ≤ n2 + n.
Kako su m i n prirodni brojevi, ovo je dalje ekvivalentno sa

1 1
n2 − n + < 2m < n2 + n + .
4 4
Ovde je od ključne važnosti bilo to što je n2 − n paran broj. Korenovanjem ove
nejednakosti dobijamo da je

1 √ 1
n− < 2m < n + ,
2 2
odnosno,
√ 1
n< 2m +< n + 1.
2
h√ i
Poslednja nejednakost važi ako i samo ako je n = 2m + 12 , gde je [ x ] oznaka
za ”ceo deo broja x”. Prema tome, formula za opšti član niza je
√ 
1
am = 2m + , m ≥ 1.
2


Zadatak 9.6. Ako je { an }n∈N aritmetički niz u kome nema elemenata jednakih
nuli, dokazati da je za svaki prirodan broj n ispunjeno:

1 1 1 n−1
+ +···+ = .
a1 a2 a2 a3 a n −1 a n a1 a n

Rešenje. Ako sa d označimo medjusobnu razliku uzastopnih članova niza, onda

za svaki prirodan broj k imamo da je
   
1 1 1 1 1 1 1 1
= = − = − .
a k a k +1 ak ( ak + d) d ak ak + d d ak a k +1

Ako sa L označimo levu stranu jednakosti koju je potrebno pokazati, imamo da

je
   
1 1 1 1 1 1 1 1 1 1
L= − + − +···+ − = −
d a1 a2 a2 a3 a n −1 a n d a1 a n
1 a n − a1 1 ( n − 1) d n−1
= · = · = .
d a1 a n d a1 a n a1 a n

 √
Zadatak 9.7. Da li brojevi 2, 5 i 5 mogu biti članovi:

(a) aritmetičkog niza;

(b) geometrijskog niza?

Rešenje. Pokažimo da je u oba slučaja odgovor negativan.

(a) Pretpostavimo da su dati brojevi članovi aritmetičkog niza. Neka je d razlika

√
uzastopnih članova
√ niza. Postoje prirodni brojevi k i l takvi da je 5 =
2 + kd
√
i 5 = 5 + ld = 2 + (k + l )d. Iz prve jednakosti dobijamo da je
5−2
d= k ∈ / Q, dok iz druge jednakosti imamo da je d = k+ 3
l ∈ Q. Prema
tome, dati brojevi ne mogu biti članovi aritmetičkog niza.

(b) Pretpostavimo da su dati brojevi članovi geometrijskog niza . Neka je q

količnik
√ uzastopnih članova niza. Postoje prirodni brojevi k i l takvi da
je 5 = 2 · qk i 5 = 2 · ql . Kvadriranjem prve jednakosti dobijamo da je
5 = 4 · q2k , pa je 4 · q2k = 2 · ql , odakle sledi da je 2 = ql −2k , odnosno
q = 21/(l −2k) . Sada je 5 = 2 · ql = ql −2k · ql = q2l −2k , pa je q = 51/(2l −2k) .
Izjednačavanjem dobijamo da je 21/(l −2k) = 51/(2l −2k) , tj., 22l −2k = 5l −2k , što
je nemoguće. Prema tome, dati brojevi ne mogu biti članovi aritmetičkog
niza.