[acm-valogato] FoxAndPhotography -- miért elég csak az első sort cserélgetni

Sziasztok! Eszembe jutott, hogyan lehet nagyon egyszerűen belátni, hogy csak az első sort elég manipulálni. Jelölje ehhez A az első és B a hátsó sort, és egy S cseresorozatot, ami (i,j) párokból áll (ahol |j-i|=1, és az indexek mindig az adott lépésben aktuális tömbre vonatkoznak). Ha B-re kellene egy S cseresorozatot alkalmazni, az ugyanaz, mintha S-et fordított sorrendben (ez legyen S') alkalmaznánk A-ra. Alkalmazzuk ugyanis S-et B-re, majd S'-t A és B-re együttesen (az egymáshoz tartozó első-hátsó párokat "összeragasztjuk"). Világos, hogy S' az S inverze is egyben, így B az eredeti sorrendre áll vissza, és az A és B-beli egymáshoz képesti viszonya rögtön az S alkalmazása után a megfelelő, az S' alkalmazása során pedig nem változott. Üdv, Balázs