Grafovi su dušu dali za ovakve zadatke.
Na sledećem grafu predstavio sam [inlmath]n[/inlmath] klovnova i [inlmath]12[/inlmath] boja, kao i veze između njih (ukoliko se neki klovn šminka određenom bojom, tada na grafu postoji veza između tog klovna i te boje, u suprotnom veza ne postoji):
- klovnovi.png (2.02 KiB) Pogledano 481 puta
Pošto stepen svakog čvora klovna iznosi najmanje [inlmath]5[/inlmath] (jer se svaki klovn šminka s bar [inlmath]5[/inlmath] boja), a čvorova klovnova ima ukupno [inlmath]n[/inlmath], to znači da zbir stepena čvorova klovnova mora biti najmanje [inlmath]5n[/inlmath]. Označimo to sa [inlmath]\sum\limits_{i=1}^n\deg(K_i)\ge5n[/inlmath].
Takođe, pošto stepen svakog čvora boje iznosi najviše [inlmath]20[/inlmath] (jer jednu boju ne sme da koristi više od [inlmath]20[/inlmath] klovnova), a čvorova boja ima ukupno [inlmath]12[/inlmath], sledi da zbir stepena čvorova boja može biti najviše [inlmath]12\cdot20[/inlmath], tj. [inlmath]240[/inlmath]. Označimo to sa [inlmath]\sum\limits_{i=1}^{12}\deg(B_i)\le240[/inlmath].
Na grafu se vidi da ove dve sume moraju biti jednake, tj. koliko se grana stiče na „levoj strani“ grafa (čvorovi klovnova), isto toliko grana mora da se stiče i na „desnoj“ strani grafa (čvorovi boja), tj.
[dispmath]\sum_{i=1}^n\deg(K_i)=\sum_{i=1}^{12}\deg(B_i)[/dispmath] pa odatle možemo pisati
[dispmath]5n\le\sum_{i=1}^n\deg(K_i)=\sum_{i=1}^{12}\deg(B_i)\le240\\
\Longrightarrow\quad5n\le240\\
\Longrightarrow\quad\enclose{box}{n\le48}[/dispmath]
Rekao bih, @Jovan111, da je to otprilike i tvoja ideja, iako tvoj postupak nisam baš uspeo do kraja da razumem.
Jovan111 je napisao:Pošto [inlmath]S\ne S'[/inlmath] implicira [inlmath]E_S\ne E_S'[/inlmath], onda ćemo imati:
[dispmath]\sum_S|E_S|=|C|=n[/dispmath]
Koliko sam razumeo oznake, [inlmath]E_S'[/inlmath] bi trebalo da predstavlja komplement skupa [inlmath]E_S[/inlmath], tj. skup svih onih klovnova koji
ne koriste boje iz [inlmath]S[/inlmath]?
I, mislim da jednakost [inlmath]\sum\limits_S|E_S|=|C|=n[/inlmath] nije tačna, da li si možda umesto toga hteo da napišeš [inlmath]\left|\bigcup\limits_SE_S\right|=|C|=n[/inlmath]?
Isto i ovde,
Jovan111 je napisao:[dispmath]|E_i|=\sum_{i\in S}|E_S|[/dispmath]
Po meni bi to trebalo da bude zapisano kao [inlmath]|E_i|=\left|\bigcup\limits_{i\in S}E_S\right|[/inlmath].
Ovaj deo nisam razumeo,
Jovan111 je napisao:i takođe da ako važi [inlmath]E_S\ne\emptyset[/inlmath], onda je [inlmath]S\ge5[/inlmath].
ali svakako zapis [inlmath]S\ge5[/inlmath] ne može biti ispravan, jer [inlmath]S[/inlmath] predstavlja skup, pa se kao takav ne može porediti s brojnom vrednošću.
Jovan111 je napisao:PS. Molio bih da teme nazivaš umesto "kombinatorika ispit" malo dopadljivije i unikatnije (da odgovaraju zadatku o kom se radi i sl. (pogledaj u pravilniku)) poput "kombinatorika - zadatak sa klovnovima"
Korigovao sam naslov. Kao što si i primetio, nije baš jednostavno za ovakav zadatak smisliti naslov koji neće delovati pomalo budalasto,
no šta da se radi.