Milutin Kojić
ELEMENTI KOMBINATORIKE
Kombinatorika je izuzetno važna oblast matematike. Ona se detaljno izučava u četvrtoj
godini kada se formulišu određene kategorije (varijacije, permutacije i kombinacije). Za
sada se čitav posao rešavanja kombinatoričkih zadataka svodi na primenu logike. Gotovo
nijedno takmičenje ne može da prođe bez bar jednog zadatka iz kombinatorike. To je pre
svega posledica toga što su kombinatorički zadaci realni, i kod učenika razvijaju
mehanizme logičkog zaključivanja. Za njihovo rešavanje nije potrebno naročito
poznavanje matematike, izuzev prostog sabiranja ili množenja.
Kao što sama reč kaže kombinatorika se bavi nekim kombinovanjem. U svakodnevnom
životu se često susrećemo sa problemima koji su čisto kombinatoričke prirode. Na
primer, kada odemo sa troje drugova ili drugarica u bioskop i kupimo četiri karte, postoji
mnogo načina kojim ćemo redosledom sesti na ta četiri mesta.
Sada ćemo razmotriti samo dva kombinatorna problema koji se u opštem slučaju, mogu
ovako formulisati:
Data su dva konačna skupa A i B, koji, redom, imaju a i b elemenata.
1) Koliko elemenata ima skup A  B ?
2) Koliko elemenata ima skup A  B ?
Odgovore na ovako postavljena pitanja nije teško dobiti. No, poteškoće mogu nastupiti
prilikom prepoznavanja problema, što je i najčešći slučaj u kombinatorici. Drugim
rečima, najteži deo posla u ovakvim zadacima neće biti primena formula, već zaključak
koju formulu treba koristiti.
Na prvo pitanje se može ovako odgovoriti: u slučaju da skupovi A i B nemaju
zajedničkih elemenata, skup A  B ima ukupno a+b elemenata; no ukoliko postoje
elementi koji pripadaju preseku tih skupova i postoji c takvih elemenata, tada skup
A  B ima ukupno (a-c)+(b-c)+c=a+b-c elemenata. Ovaj metod se u kombinatorici
naziva metodom zbira.
Drugo pitanje ima još jednostavniji odgovor: bez obzira na međusobne odnose skupova
A i B, broj elemenata skupa A  B jeste ab. Ovaj metod se naziva metodom proizvoda.
ZADACI:
1. Koliko se trocifrenih brjeva završava cifrom 3?
Rešenje: Kada bi nam neko postavio ovakvo pitanje, neki od nas bi krenuli da ispisuju
sve takve brojeve i da ih kasnije prebrojavaju. Dakle krenimo redom, prvi trocifreni broj
koji se završava cifrom 3 jeste broj 103, pa zatim 113, pa 123, i tako sve do 993. Vidimo
da bi ispisivanje svih takvih brojeva bilo dugotrajno. Ako razmislimo logički, nama je
potpuno svejedno koje će biti prve dve cifre tog broja, već nam je samo važno da
poslednja cifra bude 3. Dakle, svi ti brojevi su oblika * * 3 , gde su zvezdice označavaju
ma koje brojeve. Umesto prve zvezde mogu stajati sve cifre izuzev 0, pošto broj ne može
počinjati nulom. Umesto druge zvezdice može stajati i nula. Tako da je ukupan broj
cifara koje mogu stajati umesto prve zvezde 9, a umesto druge zvezde 10. Brojeva koji
zadovoljavaju ono što zadatak traži ima 9 10  90 .
Milutin Kojić
2. Koliko ima trocifrenih brojeva deljivih sa 5?
Rešenje: Razmišljamo slično kao u prethodnom zadatku. Da bi traženi trocifreni broj bio
deljiv sa pet, on se mora završavati ciframa 0 ili 5. Dakle, postoje dve kategorije ovih
brojeva, prvi su oblika * * 5 a drugi oblika * * 0 . Prvih ima 90 i drugih ima 90, pa ih je
ukupno 180.
3. Koliko ima četvorocifrenih brojeva, kod kojih je zbir cifara 10, a cifra desetica je
jednaka 5?
Rešenje: Naš četvorocifreni broj mora biti oblika * * 5 * . Potrebno je i da mu zbir cifara
bude jednak 10. Pošto je cifra desetice uvek 5, zbir preostale tri cifre mora biti 10-5=5.
Sada je potrebno razmotriti sve mogućnosti da je zbir tri broja jednak 5.
Mogućnosti: 1+1+3, 1+2+2. Ostale mogućnosti su istovetne kao dve navedene jer u
njima dolazi samo do pomeranja mesta ciframa što nam nije od presudnog značaja.
Prvi slučaj, tražimo broj oblika * * 5 * gde se umesto zvezdica mogu naći cifre 1,1 i 3.
Takvih mogućnosti ima samo 3, i to su brojevi 1153, 1351, 3151.
U drugom slučaju tražimo broj oblika * * 5 * gde se umesto zvezdica mogu naći cifre
1,2 i 2. Takođe ima samo tri mogućnosti i to su brojevi: 2251, 2152, 1252.
Ukupno ima 3+3=6 takvih brojeva.
4. Na pravoj p dato je pet raznih tačaka A, B, C, D, E. Koliko ima i koje su to duži čiji su
krajevi date tačke?
Rešenje: S obzirom daj e dat mali broj tačaka te duži je moguće i ispisati. To su: AB, AC,
AD, AE, BC, BD, BE, CD, CE, DE. Dakle, ima ih 10.
Međutim, šta bismo radili da nam je dato 50 tačaka i da se traži broj duži. Jasno je da je
mukotrpno sve ih ispisivati i brojati, već ćemo se poslužiti logičkim razmišljanjem. Svaka
duž je određena sa njene dve krajnje tačke. Prvu tačku biramo proizvoljno, dakle ima 5
mogućih početnih tačaka. Krajnja tačka može biti bilo koja izuzev te koju smo odabrali
za početnu, dakle ima ih 4. Logično bi bilo da je onda broj duži jednak 5  4 , tj. Da ih ima
20 ali nije! Previd je napravljen jer smo svaku duž brojali po dva puta, na primer duž AB
smo brojali i kao AB i kao BA, a mi znamo da su to dve iste duži, pa je onda potrebno
ukupan broj dobijenih duži još podeliti sa dva, jer smo svaku dva puta izbrojali, te je broj
duži 20/2=10.
5. U kupeu jednog voza nalaze se dve klupe, okrenute jedna prema drugoj, sa po pet
mesta. Od deset putnika, četiri želi da sedi u smeru kretanja voza, troje u suprotnom
smeru, a preostalima je svejedno. Na koliko načina se putnici mogu rasporediti na mesta
u kupeu?
6. Koliko ima desetocifrenih brojeva deljivih sa 25, kod kojih se cifre ne ponavljaju, ne
počinju cifrom 0, a cifra stotina im je 0 ili 5?
7. Iz grada A u grad B vodi 6 puteva, a iz grada B u grad C 3 puta. Iz grada A može se
stići u grad C jedino ako se prolazi kroz B. Na koliko različitih načina može da se putuje
iz grada A u grad C?
Milutin Kojić
8. Da bi se stiglo iz mesta A u mesto D može se proći kroz mesto B ili kroz mesto C. Od
mesta A do B vode tri direktna puta, a od A do C-četiri, od B do C-tri, od B do D-dva i
od C do D-tri direktna puta. Koliko ima mogućih puteva od A do D?
9. Od trga A do trga B vode dve jednosmerne ulice presečene sa 7 dvosmernih ulica. Na
koliko načina vozač može stići sa trga A na trg B?
10. Koliko različitih delilaca ima broj 2400?
11. Koliko ima petocifrenih brojeva koje se završavaju dvema istim ciframa?
12. Koliko ima različitih automobilskih tablica koje se sastoje iz dva slova azbuke (od 30
slova) i iza njih četvorocifrenog broja( od 0000 do 9999)?
13. U jednoj komisiji ima 7 članova. Na koliko načina se mogu izabrati predsednik,
sekretar i zapisničar te komisije?
14. Koliko na šahovskoj tabli( kvadratna mreža 8x8) ima pravougaonika?
15. Na koliko načina 8 učenika može sesti na 6 različitih stolica?
16. Koliko ima 100-cifrenih prirodnih brojeva koji se mogu zapisati pomoću cifara 0,2 i
3?
17. Koliko ima šestocifrenih prirodnih brojeva kod kojih je prva cifra paran, druga
neparan broj, treća cifra broj deljiv sa tri, četvrta prost, peta složen broj i poslednja cifra
broj koji je deljiv sa 5? (Brojevi 0 i 1 nisu ni prosti ni složeni)
18. Koliko ima sedmocifrenih brojeva čiji je zbir cifara paran?
Download

ELEMENTI KOMBINATORIKE