Feladat: F.2538 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Grallert Krisztina 
Füzet: 1986/március, 103. oldal  PDF file
Témakör(ök): Fizikai jellegű feladatok, Indirekt bizonyítási mód, Kombinatorika, Logikai feladatok, Feladat
Hivatkozás(ok):Feladatok: 1985/szeptember: F.2538

Van néhány arany és néhány ezüst érménk. Az érmék közül bármely kettő súlya különböző. Valaki sorba rendezte őket súlyuk szerint, de tévedésből a legnehezebbet nem az első, hanem az utolsó helyre rakta. (Így az 1. helyre a 2. legnehezebb, a 2. helyre a 3. legnehezebb stb. került.) Át akarjuk rendezni őket a helyes nehézségi sorrendbe, de többlet helyünk nincs, ezért egy lépésben mindig csak két (nem feltétlenül szomszédos) érmét tudunk felcserélni. Igazoljuk, hogy ha érméinket ilyen feltétel mellett átrendeztük, valamelyik lépésben egy arany és egy ezüst érmét is fel kellett cserélnünk.

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. Legyen az érmék száma k. Színezzük az 1, 2, ..., k számok mindegyikét fehérre vagy sárgára a következő módon: az i szám színe legyen fehér, ha az i-edik helyen ezüst érme áll, és sárga, ha az i-edik helyen arany érme áll. Végezzük el ezt a színezést a cserék előtt, majd minden egyes csere után is!
Ha egy lépésben ezüst érmét ezüsttel, vagy arany érmét arannyal cseréltünk fel, akkor egyetlen szám színe sem változik. Ha viszont különböző anyagú érméket cserélünk ki, akkor a két kicserélt érme helyét jelző szám színezése megváltozik. Színezésünk tehát pontosan az olyan lépések során változik, amikor arany és ezüst érmét cserélünk fel.
A feladat feltétele szerint az érmék között arany és ezüst is van, másféle pedig nincsen. Ekkor viszont a kiinduló helyzetben (és minden további helyzetben is) egymás mellett is van arany és ezüst érme. Tegyük fel, hogy kezdetben az i-edik és az (i+1)-edik helyen különböző anyagú érme áll, 1i<k. Az i-edik helyen álló érme az eljárás végén az (i+1)-edik helyre kerül, így a kiinduló helyzethez képest a véghelyzetre megváltozik az (i+1) színe. Van tehát olyan lépés, amikor i+1 színét megváltoztattuk, s ekkor a fent mondottak szerint egy arany és egy ezüst érmét cseréltünk ki.
II. megoldás. Az általánosság megszorítása nélkül föltehetjük, hogy a kezdetben utolsó helyen álló érme aranyból van. Legyen az ezüst érmék kezdeti sorszámainak összege S. Az átrendezés folyamán minden ezüst érme 1-gyel nagyobb sorszámú helyre kerül (hiszen az utolsó helyen nem ezüst áll), így az ezüst érmék sorszámainak összege S+k-ra változik.
Ha az átrendezés során ezüst érmét mindig csak ezüsttel cserélnénk fel, akkor a fenti összeg nem változhatna. Az átrendezés folyamán ezért olyan lépésnek is kell lennie, amikor ezüst érmét arannyal cseréltünk fel, s éppen ezt akartuk bizonyítani.