Dirihleov princip se često popularno ilustruje kroz "problem zečeva i kaveza".
Ako imamo 7 zečeva i 6 kaveza(ili uopšte, m zečeva i k kaveza, gde je m>k) i sve zečeve razmestimo po kavezima, onda mora postojati kavez u koji će biti smeštena bar 2 zeca.
Ako imamo 7 zečeva i 6 kaveza(ili uopšte, m zečeva i k kaveza, gde je m>k) i sve zečeve razmestimo po kavezima, onda mora postojati kavez u koji će biti smeštena bar 2 zeca.
Pretpostavimo da ne postoji takav kavez u kome su 2 zeca. Onda je u svaki od kaveza smešteno najviše po 1 zec, tako da je ukupan broj smeštenih zečeva u ovom slučaju nije veći od 1*6=6 zečeva, a ima ukupno 7 zečeva, što je protivurečno našoj pretpostavci. Kontradikcija. Znači da postoji kavez u kojem se nalazi bar 2 zeca.
Strogo formulisano, Dirihleov pricip glasi:
Ako su A i B konačni skupovi i |A|>|B|, onda ne postoji injektivno (1 na 1) preslikavanje skupa A u skup B.
Ako su A i B konačni skupovi i |A|>|B|, onda ne postoji injektivno (1 na 1) preslikavanje skupa A u skup B.
Drugačija, nešto jednostavnija formulacija Dirihleovog principa glasi :
Ako je n + 1 ili više objekata smešteno u n kutija, tada se bar u jednoj kutiji nalaze bar dva objekta.
Ako je n + 1 ili više objekata smešteno u n kutija, tada se bar u jednoj kutiji nalaze bar dva objekta.
Dokažimo ovo tvđrenje. Najpre pretpostavimo da svaka kutija sadrži najviše jedan objekat.
Tada je ukupan broj objekata najviše n, što je u suprotnosti sa pretpostavkom da
ima bar n + 1 objekata.
Tada je ukupan broj objekata najviše n, što je u suprotnosti sa pretpostavkom da
ima bar n + 1 objekata.
Opštiji oblik Dirihleovog principa može se dobiti iz principa zbira. Neka
je određeni broj objekata smešten u n kutija i neka je Ai skup objekata u kutiji,
pri čemu važi da je 1 £ i £ n. Pošto su skupovi Ai disjunktni (nemaju zajedničkih elemenata), broj objekata u kutijama je dat sa |A1| + |A2| + . . . + |An|. Stoga, ako bi se
u svakoj kutiji nalazilo najviše k objekata, tada bi ukupan broj
objekata bio najviše:
je određeni broj objekata smešten u n kutija i neka je Ai skup objekata u kutiji,
pri čemu važi da je 1 £ i £ n. Pošto su skupovi Ai disjunktni (nemaju zajedničkih elemenata), broj objekata u kutijama je dat sa |A1| + |A2| + . . . + |An|. Stoga, ako bi se
u svakoj kutiji nalazilo najviše k objekata, tada bi ukupan broj
objekata bio najviše:
k + k + . . . + k = nk.
Odnosno:
Ako je m objekata smešteno u n kutija i m > nk, tada se bar u jednoj kutiji nalazi bar k + 1 objekat.
Primer:
Koliko karata treba izvući iz špila sa 52 karte da bi se medju izvučenim kartama sigurno nalazile četiri sa istim znakom?
Izvučene karte možemo grupisati prema vrsti u 4 grupe. Da bi bili sigurni da je u jednoj od njih 4 elementa, shodno Dirihleovom principu potrebno je izvući 4 · 3+1=13 karata. Ako je broj karata manji, recimo 12, postoji mogućnost da su u te četiri grupe po tri karte, slično i za manje brojeve. Nakon 13 i više izvučenih karata (naravno ne više od 52) sigurno postoje 4 koje su istog znaka.
Izvučene karte možemo grupisati prema vrsti u 4 grupe. Da bi bili sigurni da je u jednoj od njih 4 elementa, shodno Dirihleovom principu potrebno je izvući 4 · 3+1=13 karata. Ako je broj karata manji, recimo 12, postoji mogućnost da su u te četiri grupe po tri karte, slično i za manje brojeve. Nakon 13 i više izvučenih karata (naravno ne više od 52) sigurno postoje 4 koje su istog znaka.
Literatura:
- "Kombinatorika", Dr Ratko Tošić
- "Diskretna matematika,osnove kombinatorike i teorije grafova", Dragan Stevanović,Miroslav Ćirić,Slobodan Simić,Vladimir Baltić, Beograd, 2008.
nista..
ОдговориИзбришиMeni nije jasno kako da dokazujem neki zadatak, da li recima ili brojevima i kako? Molim vas pomognite mi, sutra imam opstinsko takmicenje a ne znam ni sta ce biti, rekli su mozda i dirihleov princip,ako znate sta ce biti molim vas odgovorite mu na ovo ako uopste radi ovaj sajt. Unapred hvalaaaaaaaaaaa
ОдговориИзбришиI od ovoga je napravljena nauka? Smešno..
ОдговориИзбриши