Feladat:	B.3296	Korcsoport: 14-15	Nehézségi fok: átlagos
Megoldó(k):	Breuer János ,  Csóka Endre
Füzet:	2000/február, 98. oldal		PDF  |  MathML
Témakör(ök):	Permutációk, Feladat
Hivatkozás(ok):	Feladatok: 1999/szeptember: B.3296

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. megoldás. A sáska (S), a szöcske (SZ) és a tücsök (T) összesen hatféle elrendezésben ülhetnek egymás mellett, és minden ugrásnál a középső kicserélődik. Az alábbi gráf 6 csúcsát a 6 elrendezésnek feleltettük meg, és két csúcsot akkor kötöttünk össze, ha az egyikből 1 ugrással el lehet jutni a másikhoz, és viszont.     A csúcsokat a 0, 1, 2, 3, 4, 5 számokkal az ábra szerint megszámoztuk. 1999 ugrással pontosan akkor lehet eljutni a kiinduló sorrendhez, ha a gráf 0 pontjából az éleken lépegetve 1999 lépés után visszajuthatunk a 0 pontba. Minden lépésnél páros sorszámú csúcsból páratlanba vagy páratlanból párosba lépünk, így páratlan lépés után csak páratlan sorszámú pontba léphetünk, 0-ba nem. Tehát a feladat kérdésére a válasz: nem.  Breuer János (Budapest, ELTE Apáczai Cs. J. Gyak. Gimn., 11. o.t.)   II. megoldás. Nevezzük $A$ állapotnak az előző megoldás jelöléseit használva a következő 3 esetet: (S, SZ, T), (T, S, SZ), (SZ, T, S), $B$ állapotnak pedig a többi 3 elrendezést: (S, T, SZ), (T, SZ, S), (SZ, S, T). Minden ugrás után az $A$ állapotból a $B$-be, $B$-ből pedig az $A$-ba jutunk. Így 1999 lépés után $A$-ból kiindulva $B$-be kell jutnunk, tehát nem kerülhetünk vissza sem a kiinduló, sem a másik két $A$-beli elrendezésbe.  Csóka Endre (Debrecen, Fazekas M. Gimn., 9. o.t.)   Megjegyzés. Tetszőleges $n$ pozitív egészre $n$ elem, például az 1, 2, $\text{...}$, $n$ számok permutációit két csoportba, az úgynevezett páros és páratlan permutációkra lehet bontani. Egy tetszőleges $a_1$, $a_2$, $\text{...}$, $a_n$ permutációhoz keressük meg az összes olyan $i<j$ számpárt, amelyre $a_i>a_j$. Az ilyen párok számát hívjuk a permutáció inverziószámának. Ha az inverziószám páros, akkor a permutációt páros permutációnak nevezzük, ellenkező esetben pedig páratlan permutációnak. Ha egy permutációban két tetszőleges elemet (nem feltétlenül szomszédosokat!) felcserélünk, akkor a permutáció paritása megváltozik. A permutációk paritásának vizsgálatával 3 helyett akárhány ugrándozó rovarra is megoldható a feladat.