Matek, rendezés, segitesz?

A feladat tetszetős, a válasz igen, az oszlopok rendezése nem rontja el a sorok rendezettségét. (Amiből persze nem következik, hogy mind az 50 kártyát sorba rendeztük így).

Leegyszerűsítem a feladatot, az eredeti feladat visszavezethető a következőre: Tegyük fel, hogy x1 < x2 < x3 < x4 < x5 és x1 < x1, x2 < y2, ..., x5 < y5

Bizonyítsuk be, hogy ha az y sorozatot rendezve kapjuk az Y sorozatot, akkor x1 < Y1, x2 < Y2, ..., x5 < Y5.

Az x1 < Y1 triviális, uis ha pl. Y1 = y4, akkor x1 < x4 < y4. Hasonlóan könnyen adódik az x5 < Y5 állítás is.

Mi a helyzet pl. az x2-vel? Mivel x2 < y2, továbbá x2 < x3 < y3, x2 < x4 < y4 és x2 < x5 < y5, ezért az y sorozatban legalább 4 elem nagyobb, mint az x2. Ha az y sorozatot rendezzük (ez az Y sorozat), úgy az Y sorozat utolsó 4 eleme biztos nagyobb, mint az x2, hiszen különben nincs meg az a 4 nagyobb elem, amit az előbb láttunk. Tehát x2 < Y2 is fennáll.

Visszatérve az eredeti feladathoz az 50 kártyával: ha sorok rendezése után az oszlopok rendezését úgy hajtjuk végre, hogy az éppen rendezés alatt álló oszloppal együtt mozgatjuk a sor tőle jobbra eső (még rendezetlen) részét, mintha össze volnának kötve, akkor az előbb rendezett oszlop lapjai játszák az x sorozat szerepét, az aktuális oszlop elemei pedig az y sorozat.