RMM 2013, problema 6

[Laurențiu Ploscaru]

În fiecare vârf al unui $2n$-gon regulat este plasat câte un jeton. O mutare constă în alegerea unei laturi a poligonului și interschimbarea celor două jetoane plasate în vârfurile acesteia. După un număr finit de mutări, se constată că oricare două jetoane din configurație au fost interschimbate exact o dată. Să se arate că una dintre laturile poligonului nu a fost aleasă niciodată.

[Laurențiu Ploscaru]

Voi reformula problema. Mai întâi, voi alege un sens, să zicem cel al acelor de ceasornic. Acum să considerăm că jetoanele sunt de fapt $2n$ broaște dispuse pe un cerc. Atunci când două jetoane de pe aceeași latură se interschimbă, considerăm că o broască sare peste cea din fața ei. (desigur în sensul ales)
Avem următoarele restricții:
• O broască poate sări doar în față (în sensul stabilit);
• O broască poate sări decât peste broasca din fața ei într-o săritură;
• Dacă o broască $A$ a sărit peste $B$, atunci $A$ nu mai poate sări din nou peste $B$, nici $B$ nu va mai putea sări peste $A$;
• În momentul final, pentru orice două broaște $A$ și $B$, fie $A$ a sărit peste $B$, fie viceversa.
Lemă: Există o broască care a sărit peste toate celelalte.
Dem: Considerăm broasca ce a făcut numărul maxim de sărituri. Fie $M$ aceasta. Dacă nu ar fi sărit peste toate, ar exista o broască $N$ care a sărit peste aceasta. Până în momentul în care $N$ sare peste $M$, $N$ va fi sărit măcar peste toate broaștele peste care și $M$ a sărit, altfel nu ar fi ajuns în spatele ei. După ce sare peste $M$, $M$ va sări peste cel mult atâtea broaște ca $N$, altfel l-ar depăși. În acest caz $N$ va fi sărit peste mai multe broaște ca $M$, contradicție!
Fie $T$ broasca care a sărit peste toate, iar $S$ cea care se afla în spatele ei în momentul inițial. Voi arăta că $S$ nu a sărit peste nicio broască. Presupunem contrariul, atunci $S$ ar fi sărit peste o broască peste care $T$ sărise deja până în acel moment ($S$ nu sare peste $T$). Dar $T$ va trebui să sară peste $S$, așadar după ce va sări peste $S$, o va fi făcut încă o dată peste acea broască, pentru că se va afla în spatele lui $S$, ceea ce reprezintă o contradicție!
Acum este evident faptul că latura dintre jetoanele corespunzătoare lui $S$ și $T$ nu va fi aleasă niciodată, altfel $T$ ar face mai mult de $2n-1$ sărituri pentru a sări peste broasca care ar fi participat la interschimbarea în care ar fi fost aleasă latura respectivă.