Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI KOMBINATORIKA

Šminkanje klovnova

[inlmath]{n\choose k}=\frac{n!}{\left(n-k\right)!k!}[/inlmath]

Šminkanje klovnova

Postod Marinko » Nedelja, 07. April 2019, 19:22

1. U cirkusu radi [inlmath]n[/inlmath] klovnova. Svaki klovan se za predstavu sminka sa po bar [inlmath]5[/inlmath] od [inlmath]12[/inlmath] boja. Takodje jednu boju ne sme da koristi vise od [inlmath]20[/inlmath] klovnova. Dokazati da je [inlmath]n\le48[/inlmath].

neka moja ideja je da gledamo skup [inlmath]T(c,b)[/inlmath] i da pokusam da ga ogranicim, gde je [inlmath]c[/inlmath] - oznaka za klovna, a [inlmath]b[/inlmath] - neka od boja. Ali nikako da uspem. Ako neko ima ideju
Poslednji put menjao Daniel dana Utorak, 16. April 2019, 23:53, izmenjena samo jedanput
Razlog: Korekcija naziva teme
Marinko  OFFLINE
 
Postovi: 7
Zahvalio se: 3 puta
Pohvaljen: 0 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Re: Šminkanje klovnova

Postod Jovan111 » Nedelja, 07. April 2019, 20:30

Pozdrav! Neka je [inlmath]C[/inlmath] skup [inlmath]n[/inlmath] klovnova. Označimo boje koje se mogu koristiti sa [inlmath]1,2,3,\ldots,12[/inlmath]. Za svaku od njih ([inlmath]i=1,2,3,\ldots,12[/inlmath]) definišimo sa [inlmath]E_i[/inlmath] skup klovnova koji koriste boju [inlmath]i[/inlmath]. Za svaki podskup [inlmath]S[/inlmath] skupa [inlmath]\{1,2,3,\ldots,12\}[/inlmath] neka je [inlmath]E_S[/inlmath] skup klovnova koji koriste upravo one boje iz [inlmath]S[/inlmath]. 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] gde [inlmath]S[/inlmath] podrazumeva sve podskupove skupa [inlmath]\{1,2,3,\ldots,12\}[/inlmath]. Sada, za svako [inlmath]i[/inlmath] imamo:
[dispmath]E_S\subseteq E_i\iff i\in S[/dispmath] što nas dovodi do
[dispmath]|E_i|=\sum_{i\in S}|E_S|[/dispmath] Po uslovu zadatka znamo da je [inlmath]|E_i|\le20[/inlmath], i takođe da ako važi [inlmath]E_S\ne\emptyset[/inlmath], onda je [inlmath]|S|\ge5[/inlmath]. Iz toga što smo utvrdili imamo:
[dispmath]20\cdot12\ge\sum_{i=1}^{12}|E_i|=\sum_{i=1}^{12}\left(\sum_{i\in S}|E_S|\right)\ge5\cdot\sum_S|E_S|=5n[/dispmath]
Odatle se vidi da je [inlmath]n\le48[/inlmath].



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" :wink2:
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 136
Zahvalio se: 45 puta
Pohvaljen: 157 puta

Re: Šminkanje klovnova

Postod Daniel » Utorak, 16. April 2019, 23:53

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
klovnovi.png (2.02 KiB) Pogledano 179 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" :wink2:

Korigovao sam naslov. Kao što si i primetio, nije baš jednostavno za ovakav zadatak smisliti naslov koji neće delovati pomalo budalasto, :D no šta da se radi. :)
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 7866
Lokacija: Beograd
Zahvalio se: 4112 puta
Pohvaljen: 4184 puta

Re: Šminkanje klovnova

Postod Jovan111 » Sreda, 17. April 2019, 18:15

Daniel je napisao:
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]?

Da, da, ovde sam hteo da kažem da [inlmath]S\ne S'[/inlmath] implicira [inlmath]E_S\cap E_S'\ne\emptyset[/inlmath] iz čega sledi rečeno...

Daniel je napisao: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.

I ovde sam napravio grešku - naravno da ne možemo skup da poredimo sa brojem, već sam hteo napisati [inlmath]|S|\ge5[/inlmath] :D
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 136
Zahvalio se: 45 puta
Pohvaljen: 157 puta

Re: Šminkanje klovnova

Postod Daniel » Četvrtak, 18. April 2019, 09:30

Jovan111 je napisao:već sam hteo napisati [inlmath]|S|\ge5[/inlmath] :D

OK, ispravio sam ti ovaj deo. Mislim da s tom ispravkom (donekle) kapiram šta je zapravo skup [inlmath]E_S[/inlmath] i, ako sam dobro razumeo (što ne tvrdim sa sigurnošću), onda ovaj deo rečenice
Jovan111 je napisao:Za svaki podskup [inlmath]S[/inlmath] skupa [inlmath]\{1,2,3,\ldots,12\}[/inlmath] neka je [inlmath]E_S[/inlmath] skup klovnova koji koriste upravo one boje iz [inlmath]S[/inlmath].

zapravo kaže da je [inlmath]E_S[/inlmath] skup onih klovnova za čije se šminkanje sve potrebne boje nalaze u [inlmath]S[/inlmath] (ni sâm ne znam kako da ovo sročim jednostavnije).

Ali onda mi u tom mom shvatanju opet nešto nije logično, jer ako bismo recimo uzeli da je [inlmath]S[/inlmath] jednak skupu svih boja (što smemo, jer nije rečeno da [inlmath]S[/inlmath] mora biti pravi podskup skupa boja), tada bi [inlmath]E_S[/inlmath] bio jednak skupu svih klovnova? Ako je tako, onda ekvivalencija [inlmath]E_S\subseteq E_i\iff i\in S[/inlmath] ne bi važila, jer u tom slučaju bilo koje [inlmath]i[/inlmath] svakako pripada skupu [inlmath]S[/inlmath], a opet, [inlmath]E_i[/inlmath] ne može biti nadskup celog skupa boja...

Mada, kažem, moguće da nisam ovo baš razumeo, ali uostalom i nije previše bitno, izložena su dva načina za rešavanje ovog zadatka, pa ko želi da se bavi ovim zadatkom može da bira...
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 7866
Lokacija: Beograd
Zahvalio se: 4112 puta
Pohvaljen: 4184 puta

Re: Šminkanje klovnova

Postod Jovan111 » Četvrtak, 18. April 2019, 21:02

Daniel je napisao:OK, ispravio sam ti ovaj deo. Mislim da s tom ispravkom (donekle) kapiram šta je zapravo skup [inlmath]E_S[/inlmath] i, ako sam dobro razumeo (što ne tvrdim sa sigurnošću), onda ovaj deo rečenice
Jovan111 je napisao:Za svaki podskup [inlmath]S[/inlmath] skupa [inlmath]\{1,2,3,\ldots,12\}[/inlmath] neka je [inlmath]E_S[/inlmath] skup klovnova koji koriste upravo one boje iz [inlmath]S[/inlmath].

zapravo kaže da je [inlmath]E_S[/inlmath] skup onih klovnova za čije se šminkanje sve potrebne boje nalaze u [inlmath]S[/inlmath] (ni sâm ne znam kako da ovo sročim jednostavnije).

Da, baš tako treba da bude, iako moram reći da nisam
Daniel je napisao:Ali onda mi u tom mom shvatanju opet nešto nije logično, jer ako bismo recimo uzeli da je [inlmath]S[/inlmath] jednak skupu svih boja (što smemo, jer nije rečeno da [inlmath]S[/inlmath] mora biti pravi podskup skupa boja), tada bi [inlmath]E_S[/inlmath] bio jednak skupu svih klovnova? Ako je tako, onda ekvivalencija [inlmath]E_S\subseteq E_i\iff i\in S[/inlmath] ne bi važila, jer u tom slučaju bilo koje [inlmath]i[/inlmath] svakako pripada skupu [inlmath]S[/inlmath], a opet, [inlmath]E_i[/inlmath] ne može biti nadskup celog skupa boja...

razmišljao o ovome, pa pretpostavljam da bi ispravnije bilo da sam rekao pravi podskup umesto podskup.
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 136
Zahvalio se: 45 puta
Pohvaljen: 157 puta


Povratak na KOMBINATORIKA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 6 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Ponedeljak, 17. Februar 2020, 17:07 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs