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

Pogadjanje kartica

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

Pogadjanje kartica

Postod petarn » Petak, 25. Maj 2018, 03:23

Unapred se izvinjavam ako ovo pitanje ne treba da bude u kombinatorici, nisam siguran koja je ovo oblast.

Da li neko može da mi da formulu za rešavanje sledećeg zadatka (samo obrazac, ne treba dodatno objašnjenje):

Na stolu se nalazi [inlmath]n[/inlmath] kartica. Svaka kartica na sebi ima ispisan broj [inlmath]0[/inlmath] ili [inlmath]1[/inlmath]. Kartice su okrenute naopačke i ne vidi se koja kartica na sebi ima ispisano [inlmath]0[/inlmath], a koja [inlmath]1[/inlmath].

[inlmath]2^n[/inlmath] ljudi pogađa broj za svaku karticu.
Svi su se dogovorili da svako izabere jedinstvenu kombinaciju.

Koliko ljudi ce pogoditi broj za tačno [inlmath]x[/inlmath] kartica?

Da pojasnim zadatak na primeru:
Ima [inlmath]5[/inlmath] kartica, pogađa [inlmath]32[/inlmath] čoveka, niko nije pogađao za svaku karticu isto kao neko drugi, koliko njih ce pogoditi broj za tačno [inlmath]3[/inlmath] kartice?

Hvala unapred.
Petar
Poslednji put menjao Daniel dana Petak, 25. Maj 2018, 12:42, izmenjena samo jedanput
Razlog: Dodavanje Latex-tagova (tačka 13. Pravilnika)
petarn  OFFLINE
 
Postovi: 2
Zahvalio se: 0 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: Pogadjanje kartica

Postod Daniel » Petak, 25. Maj 2018, 12:43

Izbor rubrike je OK, ovo je tipičan zadatak iz kombinatorike. :)

Dodao sam Latex-tagove u tvoj post, kako bi brojne vrednosti i oznake bile uočljivije u odnosu na ostatak teksta. To je, uostalom, i predviđeno Pravilnikom foruma, koji bih te pozvao da pročitaš, ukoliko nisi.

Nije ideja foruma da dajemo gotova rešenja ili gotove obrasce, već da pomognemo korisnicima da sami do njih dođu.
Da li možeš, za početak, reći koliko postoji različitih mogućnosti za raspored nula i jedinica na karticama? Odgovor na ovo pitanje olakšaće nalaženje odgovora koji se traži u zadatku.
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: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta

Re: Pogadjanje kartica

Postod petarn » Petak, 25. Maj 2018, 23:46

Hvala na odgovoru.

Nisam hteo nikoga da gnjavim, pa rekoh samo rešenje mi je dovoljno, a trebaće mi vremena da ukapiram (nisam mnogo pametan :) ).

Ima upravo [inlmath]2^n[/inlmath] mogućnosti, i svaki čovek izabere jednu od tih mogućnosti (svi različitu). Znam da će jedan čovek pogoditi sve, jedan će promašiti sve; kad su manji brojevi u pitanju, mogu da ispišem sve mogućnosti i da prebrojim koliko će ko pogoditi, ali ne mogu nikako da izvedem obrazac za opšti slučaj.
petarn  OFFLINE
 
Postovi: 2
Zahvalio se: 0 puta
Pohvaljen: 0 puta

Re: Pogadjanje kartica

Postod Daniel » Nedelja, 27. Maj 2018, 15:25

Tako je, [inlmath]2^n[/inlmath] mogućnosti. Znači, svaka od mogućih kombinacija naći će se među ponuđenim odgovorima, i nijedna od mogućih kombinacija ne može se pojaviti u dva ili više ponuđena odgovora.

Hajde za početak da razmotrimo koliko prisutnih će pogoditi broj na svih [inlmath]n[/inlmath] kartica. Odgovor je, naravno – jedna osoba (kao što si i zaključio), jer pošto su svi dali odgovore za različite kombinacije, i pošto su svim odgovorima pokrivene sve moguće kombinacije, to znači da će onu „pravu“ kombinaciju imati tačno jedna osoba.
Isti je odgovor i ako pitamo koliko prisutnih će pogoditi broj na [inlmath]0[/inlmath] kartica. Jedna osoba, jer će uvek postojati jedna osoba koja će u svom odgovoru imati sve komplementarne brojeve od onog tačnog. Npr. ako je stanje [inlmath]10010[/inlmath], tačno jedna osoba će imati odgovor [inlmath]01101[/inlmath].
Zasad, dakle, imamo odgovore za sledeće slučajeve:
[dispmath]\begin{array}{c|c|c|c|c|c|c|c|c|c|c}
\begin{matrix} \text{Broj karata}\\ \text{koje treba pogoditi} \end{matrix} & 0 & 1 & 2 & 3 & \cdots & x & \cdots & n-2 & n-1 & n\\ \hline
\begin{matrix} \text{Broj osoba koje će pogoditi}\\ \text{zadati broj karata} \end{matrix} & 1 & & & & \cdots & & \cdots & & & 1
\end{array}[/dispmath] Sad za nijansu teže pitanje – koliko prisutnih će pogoditi broj na tačno [inlmath]n-1[/inlmath] kartica (tj. na svim pozicijama osim na jednoj). Tačno jedna osoba će pogrešiti broj na prvoj poziciji a brojeve na svim ostalim pozicijama pogoditi; zatim, tačno jedna osoba će pogrešiti broj na drugoj poziciji a brojeve na svim ostalim pozicijama pogoditi... i tako do [inlmath]n[/inlmath]-te pozicije. Zaključujemo da će [inlmath]n[/inlmath] osoba pogoditi broj na tačno [inlmath]n-1[/inlmath] kartica.
Analogno, kao i u prethodnom slučaju, posmatrajući komplementarne brojeve zaključujemo i da će [inlmath]n[/inlmath] osoba pogoditi tačno jedan broj:
[dispmath]\begin{array}{c|c|c|c|c|c|c|c|c|c|c}
\begin{matrix} \text{Broj karata}\\ \text{koje treba pogoditi} \end{matrix} & 0 & 1 & 2 & 3 & \cdots & x & \cdots & n-2 & n-1 & n\\ \hline
\begin{matrix} \text{Broj osoba koje će pogoditi}\\ \text{zadati broj karata} \end{matrix} & 1 & n & & & \cdots & & \cdots & & n & 1
\end{array}[/dispmath] Već sada možemo naslutiti nekakvu simetričnost rezultata u odnosu na polovinu broja [inlmath]n[/inlmath] (tj. [inlmath]1,n,\cdots, n,1[/inlmath]).

Idmeo dalje. Koliko prisutnih će pogoditi broj na tačno [inlmath]n-2[/inlmath] kartica (tj. na svim pozicijama osim na dve)? Ako sa [inlmath]-[/inlmath] označimo promašen broj na kartici a sa [inlmath]+[/inlmath] pogođen broj na kartici, imamo da će tačno jedna osoba dati odgovor [inlmath]--+++\cdots++[/inlmath], tačno jedna će dati odgovor [inlmath]-+-++\cdots++[/inlmath]... Tačno jedna će dati odgovor [inlmath]+--++\cdots++[/inlmath] itd. Znači, pitanje možemo svesti na to na koliko načina možemo ova dva minusa rasporediti na ukupno [inlmath]n[/inlmath] pozicija (tj. na koliko načina od ukupno [inlmath]n[/inlmath] pozicija možemo odabrati one na kojima odgovor treba da bude pogrešan, a na svim ostalim tačan). To su kombinacije bez ponavljanja od [inlmath]n[/inlmath] elemenata [inlmath]2.[/inlmath] klase, a njihov broj je [inlmath]n\choose2[/inlmath]:
[dispmath]\begin{array}{c|c|c|c|c|c|c|c|c|c|c}
\begin{matrix} \text{Broj karata}\\ \text{koje treba pogoditi} \end{matrix} & 0 & 1 & 2 & 3 & \cdots & x & \cdots & n-2 & n-1 & n\\ \hline
\begin{matrix} \text{Broj osoba koje će pogoditi}\\ \text{zadati broj karata} \end{matrix} & 1 & n & & & \cdots & & \cdots & \displaystyle{n\choose2} & n & 1
\end{array}[/dispmath] Bi li umeo sad odavde da izvedeš izraz i za ostale slučajeve, kao i za onaj opšti (koji se u zadatku traži) da je potrebno pogoditi broj za tačno [inlmath]x[/inlmath] kartica? Možeš se služiti osobinom binomnog koeficijenta da je [inlmath]{n\choose n-k}={n\choose k}[/inlmath].
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: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta


Povratak na KOMBINATORIKA

Ko je OnLine

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


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 12:37 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs