Feladat: Gy.2712 Korcsoport: 14-15 Nehézségi fok: átlagos
Megoldó(k):  Fehér Ágnes 
Füzet: 1992/február, 70 - 71. oldal  PDF  |  MathML 
Témakör(ök): Permutációk, Gyakorlat
Hivatkozás(ok):Feladatok: 1991/szeptember: Gy.2712

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.

A feladat egyértelműsége érdekében először is definiáljuk a helyezés, illetve a helyezésváltozás jelentését holtversenyes helyzetekre a következőképpen: csak a tényleges előzéseket tekintsük helyezésváltozásnak. Azaz, ha például X az első, Y a második helyen állt és Y utolérte X-et, X helyezése továbbra is az első, Y-é a második. Váltás csak akkor történik, ha Y le is hagyja X-et. Ennek fényében, ha X utolérte Y-t, majd ők ketten egyszerre megelőzték Z-t, akkor először (ZYX) a sorrend, az előzés során előbb (YZX), majd (YXZ). Tehát Z helyezése kétszer, a többieké egyszer-egyszer változott eközben. Ily módon minden helycserét pontosan két versenyző közti eseménynek tekintünk; továbbá nincs holtverseny, ugyanis két egymás mellett levő versenyző közül az utolért futót még előrébb levőnek vesszük.
Rátérve a feladat megoldására, a szöveg szerint a rajt után közvetlenül XYZ volt a sorrend. Ha valamelyikük helyezése egyszer megváltozott, akkor csak ellentétes paritásúvá válhatott. Ennélfogva páratlan számú helyváltoztatás esetén a kezdetivel ellentétes paritású helyre jutott, páros számú cserével pedig azonos paritásúra.
Mivel először X az első volt és helyezése páratlanszor változott, így csak páros számú helyen érhetett a célba, azaz ő lett a második. Az utolsó feltétel szerint Y megelőzte X-et, ezért ő csak a nyertes lehetett, míg Z-nek a harmadik hely jutott. A következő példa egy lehetőséget mutat az egymás utáni sorrendváltozásokra:

  IXXXYYYYY IIYZYXZXZXIIIZYZZXZXZ


Láthatóan X helyezése ötször, Z helyezése hatszor változott ‐ ez utóbbira egyébként nem is volt szükségünk a feltételek közül (de ellentmondásra vezetett volna, ha Z helyezése is páratlan sokszor változott volna).
 
Megjegyzés. Ha a holtversenyes helyzeteket nem a fenti módon kezelnénk, a  megoldás nem feltétlenül lenne egyértelmű. Például az IXII-IIIZ,YI-IIZ,YIIIX cserénél, ha X helyezését úgy tekintjük, hogy csak egyszer változott, akkor X páratlan  helyezésével a kiindulásival megegyező paritású helyre került, s így nem szükségszerű, hogy a versenyben ő lett a második. Példa erre a következő:
IIIXXZXZXIIYZXZXIIIZYYYY}Y,Z}Y,ZX
Fehér Ágnes (Miskolc, Földes F. Gimn., I. o. t.)
dolgozata alapján