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

Broj najkraćih puteva od a1 do h8

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

Broj najkraćih puteva od a1 do h8

Postod Loophoop » Petak, 26. Maj 2017, 11:54

Zdravo

Koliko ima najkraćih putanja na šahovskoj tabli od polja a1 do polja h8, ako se kretanje vrši isključivo nadesno ili naviše?

Ima i resenje
U oba slucaja je logika da imamo [inlmath]7[/inlmath] horizontalnih pokreta i [inlmath]7[/inlmath] vertikalnih

Prvo resenje
[dispmath]14\choose7[/dispmath] Drugo resenje
[dispmath]\frac{14!}{7!\cdot7!}[/dispmath] Ne razumem prvo resenje
Procitao sam na ovom fourumu tutorijal o kombinaciji bez ponavljanja
I tamo stoji da je
To isto kao varijacije bez ponavljanja samo podeljeno sa faktorijal od broja elementa
I to je ok za mene
Ali recimo pocnimo od varijacije bez ponavljanja, tamo pise za [inlmath]V_n^1[/inlmath]
I tu biramo samo jedan element, pa je resenje [inlmath]n[/inlmath]

I sad jos to podelimo sa [inlmath]k![/inlmath]
I dobijemo resenje, kombinacije bez ponavljanja

Ali nije mi jasno kod prvog resenja zasto biramo [inlmath]7[/inlmath] elemenata od [inlmath]14[/inlmath]
Nama treba minimum [inlmath]14[/inlmath] poteza da stignemo u gornji desni ugao
Pa mi nelogicno zasto biramo samo [inlmath]7[/inlmath]

*ova resenja su verovatno 80% tacna, nisam ih uporedjivao sa jednako, jer me ne zanima da li su jednaka, samo me zanima kako smo dosli do njega

Drugo resenje
Ovde je fora da imamo dva skupa, jedan sa [inlmath]7[/inlmath] horizontalna poteza, i drugi sa [inlmath]7[/inlmath] vertik...
Pa je resenje prvo napravimo sve permutacije [inlmath]14![/inlmath], pa onda podelimo sa permutacijama skupova [inlmath](7!)^2[/inlmath], da bi dobili permutacije sa ponavljanjem?
Poslednji put menjao Corba248 dana Petak, 26. Maj 2017, 13:16, izmenjena samo jedanput
Razlog: Promena naziva teme
 
Postovi: 10
Zahvalio se: 4 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: Broj najkraćih puteva od a1 do h8

Postod Corba248 » Petak, 26. Maj 2017, 12:38

Loophoop je napisao:*ova resenja su verovatno 80% tacna, nisam ih uporedjivao sa jednako, jer me ne zanima da li su jednaka, samo me zanima kako smo dosli do njega

Naravno da su jednaka, kad raspišeš ovaj binomni koeficijent iz prvog rešenja dobijaš upravo ovo drugo rešenje.

Loophoop je napisao:Ne razumem prvo resenje

Mi upravo biramo od tih [inlmath]14[/inlmath] mogućih poteza [inlmath]7[/inlmath] od jedne vrste, recimo nadesno. Ostali potezi biće uslovljeni sa ovih [inlmath]7[/inlmath]. Ako su nam, na primer, prvi, treći, četvrti, peti, sedmi, deseti i četrnaesti potez nadesno onda znamo i koji su nam potezi naviše.

Drugo rešenje si i sam dobro objasnio. Pomoću permutacija sa ponavljanjem. Dakle, [inlmath]14[/inlmath] mogućih poteza možemo načiniti na [inlmath]14![/inlmath] načina, ali pošto su nam po [inlmath]7[/inlmath] istih ukupan broj načina ([inlmath]14![/inlmath]) moramo podeliti sa [inlmath](7!)^2[/inlmath].

U ovom zadatku je zapravo ključno uočiti da moramo imati tačno [inlmath]7[/inlmath] poteza naviše i tačno [inlmath]7[/inlmath] poteza nadesno.
Zaslužni forumaš
 
Postovi: 314
Zahvalio se: 37 puta
Pohvaljen: 352 puta

  • +1

Re: Broj najkraćih puteva od a1 do h8

Postod Daniel » Petak, 26. Maj 2017, 14:20

Možemo i ovako da posmatramo:
Loophoop je napisao:Prvo resenje
[dispmath]14\choose7[/dispmath]

Obeležimo horizontalne pokrete sa [inlmath]H[/inlmath], a vertikalne sa [inlmath]V[/inlmath]. Napišemo zatim pokrete onim redosledom kojim su bili odigrani. Neke od mogućnosti su:
[dispmath]\begin{matrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\
V & H & H & H & V & H & V & V & H & V & V & H & H & V\\
H & V & V & H & V & V & H & V & H & H & V & H & V & H\\
V & H & V & H & H & V & H & V & V & V & H & V & H & H
\end{matrix}\\
\vdots[/dispmath] U prvom slučaju [inlmath]H[/inlmath]-pokret smo odigrali u potezima [inlmath]2,3,4,6,9,12,13[/inlmath] (ukupno [inlmath]7[/inlmath]). U drugom slučaju to su bili potezi [inlmath]1,4,7,9,10,12,14[/inlmath] (takođe ukupno [inlmath]7[/inlmath]). U trećem slučaju to su bili potezi [inlmath]2,4,5,7,11,13,14[/inlmath] (isto [inlmath]7[/inlmath]). Možemo primetiti da od ukupno [inlmath]14[/inlmath] rednih brojeva poteza biramo onih [inlmath]7[/inlmath] rednih brojeva poteza u kojima ćemo odigrati [inlmath]H[/inlmath]-pokret. Broj načina na koje od [inlmath]14[/inlmath] brojeva možemo odabrati njih [inlmath]7[/inlmath] upravo je broj kombinacija bez ponavljanja od [inlmath]14[/inlmath] elemenata klase [inlmath]7[/inlmath], tj. [inlmath]14\choose7[/inlmath].
Naravno, isti rezultat bismo dobili i da smo umesto [inlmath]H[/inlmath]-poteza posmatrali [inlmath]V[/inlmath]-poteze, jer i jednih i drugih ima po [inlmath]7[/inlmath].

Loophoop je napisao:Drugo resenje
[dispmath]\frac{14!}{7!\cdot7!}[/dispmath]

Ispravno ste odgovorili i ti i Corba248. Dakle, upravo u temi koju si pomenuo data je formula za permutacije s ponavljanjem, [inlmath]\overline P_n^{n_1,n_2,\ldots ,n_m}=\frac{n!}{n_1!\cdot n_2!\cdots n_m!}[/inlmath], i detaljno je opisano njeno izvođenje. Samo je potrebno u tu formulu uvrstiti brojne vrednosti, [inlmath]n=14[/inlmath] (ukupan broj poteza), [inlmath]n_1=7[/inlmath] (broj [inlmath]H[/inlmath]-poteza) i [inlmath]n_2=7[/inlmath] (broj [inlmath]V[/inlmath]-poteza). Naravno, ispunjeno je [inlmath]n=n_1+n_2[/inlmath]. Sledi [inlmath]\overline P_{14}^{7,7}=\frac{14!}{7!\cdot7!}[/inlmath].

Loophoop je napisao:*ova resenja su verovatno 80% tacna, nisam ih uporedjivao sa jednako, jer me ne zanima da li su jednaka,

:?: :shock:
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: Broj najkraćih puteva od a1 do h8

Postod Loophoop » Petak, 26. Maj 2017, 19:29

*nisam siguran da se ovako citira, i navodi osoba kojoj je upucena poruka

@Corba248:
Ostali potezi biće uslovljeni sa ovih [inlmath]7[/inlmath].

Ne razumem kako ce biti uslovljeni sa ovih [inlmath]7[/inlmath], kad posle bilo kog poteza recimo horizontalno, mi mozemo da odigramo opet horizontalno ili vertikalno

@Daniel
Jedno resenje je iz zbirke a drugo iz sveske, pa navodim veliki procenat da su tacna resenja
Pa pored toga da su verovatno jednaka, mene jos i ne zanima da li su
To sam naveo jer sam video dosta postova po internetu, gde je pocetak ili ceo odgovor, na foru uporedi ih sa jednako
 
Postovi: 10
Zahvalio se: 4 puta
Pohvaljen: 0 puta

Re: Broj najkraćih puteva od a1 do h8

Postod Daniel » Subota, 27. Maj 2017, 08:17

Loophoop je napisao:*nisam siguran da se ovako citira, i navodi osoba kojoj je upucena poruka

Kod svakog posta imaš dugme „Citiraj“ – klikneš na njega i iz citata (koji će automatski biti uokviren Quote-tagovima) ukloniš onaj deo teksta koji nije bitan i koji ne treba da se nalazi u citatu, a ostaviš samo onaj deo teksta na koji odgovaraš.

Loophoop je napisao:@Daniel
Jedno resenje je iz zbirke a drugo iz sveske, pa navodim veliki procenat da su tacna resenja
Pa pored toga da su verovatno jednaka, mene jos i ne zanima da li su
To sam naveo jer sam video dosta postova po internetu, gde je pocetak ili ceo odgovor, na foru uporedi ih sa jednako

Hajde sad lepo iščitaj ovo što si napisao, stavivši se u poziciju nekog ko treba, čitajući to, da shvati šta si želeo da kažeš. :shock:
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 40 gostiju


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