Pozdrav, evo zadatka koji je bio na prijemnom na PMFu u Novom Sadu 2009. Ja nisam uspeo da ga resim

Na koliko nacina [inlmath]5[/inlmath] decaka, Adam, Bojan, Cira, Dejan i Emil, i [inlmath]4[/inlmath] devojcice, Fiona, Goca, Hermiona i Ivana, mogu da sednu oko okruglog stoIa, ali tako da Cira i Fiona ne sede jedno pored drugog?

Pozdrav, Dzenane!

Možda ti ovaj zadatak bude od pomoći.

Dobro došao, Dzenane! Zamolio bih te da se upoznaš sa pravilnikom ovog foruma, posebno sa tačkom 6.

Što se konkretnog zadatka tiče- najlakše ga je rešiti tako što oduzmeš broj načina pri kojem ovo dvoje sede jedno do drugog od ukupnog broja načina da se svi oni rasporede.
Prema smernici koju je Stevan dao lako ćeš to uraditi- prvo je [inlmath]8![/inlmath], a drugo [inlmath]7![/inlmath]

Traženi broj načina je, dakle, [inlmath]8!-7!=35280[/inlmath].

Hvala na dobrodošlici i na odgovorima.
I ja sam razmišljao na taj način i palo mi je još ideja na pamet, samo što nisam znao broj permutacija kad ovo dvoje sede jedno do drugog.
Mislio sam i broj dijagonala kod mnogougla [inlmath]\frac{n(n - 3)}{2}[/inlmath] pomnožen sa permutacijama kad ostalih [inlmath]7[/inlmath] sedi između i okolo njih.

Dobrodošlica i od mene!

Zapravo, od [inlmath]8![/inlmath] treba oduzeti [inlmath]2\cdot 7![/inlmath] a ne [inlmath]7![/inlmath], budući da postoje dva slučaja – jedan je da Fiona sedi levo od Ćire, a drugi je da Fiona sedi desno od Ćire. U svakom od ta dva slučaja posmatramo Fionu i Ćiru kao jednu osobu (budući da ih tretiramo kao da su „fiksirani“ jedno uz drugo), pa broj rasporeda tražimo kao broj rasporeda po krugu od [inlmath]8[/inlmath] osoba, a to je [inlmath]7![/inlmath]. Znači, [inlmath]7![/inlmath] u jednom slučaju, plus [inlmath]7![/inlmath] u drugom slučaju – to je [inlmath]2\cdot 7![/inlmath]. Oduzmemo to od [inlmath]8![/inlmath] i to je
[dispmath]8!-2\cdot 7!=8\cdot 7!-2\cdot 7!=\left(8-2\right)7!=6\cdot 7![/dispmath]
Moglo bi se posmatrati i kao dijagonale u mnogouglu, to si se dobro setio, budući da dijagonale mogu spajati samo temena koja nisu susedna. Samo, ne treba ti cela formula za broj dijagonala, već samo [inlmath]n-3[/inlmath], tj. broj dijagonala koje je moguće povući iz jednog temena. To je zbog toga što jedno od to dvoje, Fionu ili Ćiru, fiksiramo – ajd recimo da fiksiramo Fionu – pa zatim gledamo na koliko načina je moguće postaviti Ćiru da ne bude pored Fione. Moguće ga je postaviti upravo na [inlmath]n-3[/inlmath] načina gde je [inlmath]n[/inlmath] broj osoba, znači, na [inlmath]6[/inlmath] načina. U svakom od tih [inlmath]6[/inlmath] slučajeva, preostalih [inlmath]7[/inlmath] osoba je moguće rasporediti, kako si i sâm primetio, na [inlmath]7![/inlmath] načina. Znači, i na taj način dobijamo [inlmath]6\cdot 7![/inlmath] mogućnosti.

Iako se to u zadatku ne traži, nije nikakav problem rešenje dati i u opštem slučaju, kada imamo [inlmath]n[/inlmath] osoba, a dve od tih [inlmath]n[/inlmath] osoba ne smeju biti jedna pored druge. Tada je rešenje
[dispmath]\left(n-1\right)!-2\left(n-2\right)!=\left(n-1\right)\left(n-2\right)!-2\left(n-2\right)!=\left[\left(n-1\right)-2\right]\left(n-2\right)!=\left(n-3\right)\left(n-2\right)![/dispmath]
a posmatranjem dijagonala u mnogouglu do tog rešenja se čak dolazi i mnogo brže – u jednom koraku.

Da, moja greška, trebalo je biti samo [inlmath]n-3[/inlmath] jer je to broj dijagonala iz jednog temena a ovo što sam ja napisao je ukupan broj dijagonala.
Hvala na odgovoru, sad je jasno!

Da se nadovežem na svoj prvobitni odgovor- a ujedno i ispravim, jer bi prvi broj rasporeda bio [inlmath]\frac{8!}{2}[/inlmath] logikom kojom sam ja išao, a onda ukupan broj mogućih raspreda [inlmath]\frac{8!}{2}-7![/inlmath].
E sad, da pojasnim na šta ciljam. Ono što je Daniel naveo jedan raspored i njegov odraz u ogledalu tretira kao dva različita rasporeda, dok se meni učinilo logičnim da to smatram istim raspredom.
Da pojasnim:


Neka su Fiona i Ćira F i Ć u ovom pravougaoniku, a neka je ovih ostalih sedam obeleženo sa A, B, C, D, E, F, G. Slučaj 1 sa slike je kad Fiona sedi s jedne strane.. Međutim u slučaju 4 Fiona sedi s druge strane od Ćire, a ako ispremeštamo ove ostale dobijamo potpuno isti raspored kao u u slučaju 1 (samo pratite strelice i čitaćete istu "reč"). Slično, važi i za slučajeve 2 i 3.

Primedba svakako ima logike – padalo je meni sinoć to isto na pamet, čak mi se i čini da je zadatak donekle nejasno formulisan, jer bi svakako trebalo u tekstu naglasiti da li se jedan raspored i njemu "mirrored" raspored računaju kao jedan isti slučaj ili ne. Ipak, po nekoj analogiji sa zadatkom na koji je stevan95 linkovao, a u kojem je kao ispravno rešenje navedeno [inlmath]6[/inlmath], tj. [inlmath]3![/inlmath], koje odgovara tumačenju po kojem se jedan raspored i njegov lik u ogledalu razmatraju kao dva različita rasporeda, smatrao sam logičnim da se takav rezon primeni i ovde.

Osim toga, iako je tačno da će u takvim parovima slučajeva svaka od osoba biti između iste dve osobe, ipak će ona osoba koja je u prvom slučaju bila levo od posmatrane osobe – u drugom slučaju biti desno od nje, kao i obratno, što takve rasporede ipak čini različitim. (Da malo to i ilustrujem jednim šaljivim primerom – ako je osoba [inlmath]D[/inlmath], recimo, potpuno gluva na desno uho, a omiljeni sagovornik joj je [inlmath]E[/inlmath], sigurno je da osobi [inlmath]D[/inlmath] neće biti svejedno hoće li biti raspoređeni prema slici 1 ili prema slici 4 – nepogodniji će joj biti raspored na slici 1 na kojem je [inlmath]E[/inlmath] s njene desne strane, za razliku od rasporeda na slici 4 kada će joj [inlmath]E[/inlmath] biti s leve strane i kada će je, prema tome, bez problema čuti. )

Ipak, kada je u zadatku tačno naglašeno da se ta dva rasporeda razmatraju kao jedan, neće ni biti teško modifikovati ovo rešenje koje sam ja dao – samo ga treba podeliti sa [inlmath]2[/inlmath].