zadatak

[hexy]

Može mi netko objasniti i rješiti zadatak :

Pustinjom putuje karavana od 9 deva. Nakon odmora u oazi treba promijeniti redoslijed deva tako da niti jedna deva ne hoda iza one iza koje je hodala prije.Na koliko načina se to može napraviti ?

PUNO HVALA i sretno svima na ispitima

[veky]

[Nesi]

da odgovorim, ako nije prekasno
dakle, imas lanac deva... npr
1-2-3-4-5-6-7-8-9
ok?

e sad, ukupan broj nacina na koji ih mozes vodati pustinjom je 9! = 362880
promatrat cemo ove crtice medju devama - zamisli da se svaka deva osim prve drzi onoj drugoj za rep
A_i neka je skup kada je i. deva IZA (i-1). (dakle, i ide od 2 do 9)
gledamo skup A_2 znaci, imamo (1-2)-3-4-5-6-7-8-9
takvih nacina ima 8! jer imamo 8 deva (multideva i ostale deve ) koje permutiramo
to smo zapravo gledali vezu izmedju neke dvije deve - takvih veza mozemo birati (8 povrh 1) - od 8 mogucih biramo jednu

e sad, A_1 presjek A_2 nam je isto kao A_1 presjek A_3
zasto?
jer u oba slucaja imamo dvije veze, nije bitno da li se radi o velikom multiskupu od tri deve, ili od dva multiskupa od dvije deve i ostalih - to sve mozemo permutirati na 7! nacina i te dvije veze odabrati na (8 povrh 2) nacina
i samo na jedan nacin (8 povrh *1! mozemo odabrati sve veze

dakle, ukupan broj nevaljalih pozicija - tu ide FUI je:
(8 povrh 1)*8! - (8 povrh 2)*7! + (8 povrh 3)*6! - (8 povrh 4)*5! + (8 povrh 5)*4! - (8 povrh 6)*3! + (8 povrh 7)*2! - (8 povrh *1! = 214551

broj nacina na koji deve mozemo poslagati u kolonu a da zadovoljimo uvjet zadatka je : 362880 - 214551 = 148329 sto je Krcko na vjezbama i rekao da je rjesenje

_________________
It's not who you love. It's how.