Hogyan oldjam meg ezt a bizonyításos sorbarendezési feladatot?

nem vagyok jó az elméletben, de:

problémaredukcióval érdemes próbálkozni, szerintem.

vegyünk, egy 2x2-es téglalapot (négyzetet)

tegyük fel, hogy az első lépés után így néz ki a helyzet:

ab

cd

tudjuk, hogy b>=a és d>=c, mivel ez az első lépés kritériuma, vagy mi.

ha a<=c, akkor az első oszlop marad, ha b<=d akkor a második is marad, és mivel az első lépésben sorba rendeztünk a sorokban, nem történt változás, ezért sorba vannak.

ha a<=c, de b>d, akkor ez lesz:

ad

cb

Mivel a<=c, c<=d az első lépés miatt, ezért a<=d, tehát az ab sor az fasza. (a<=c<=d)

d>=c az első lépés miatt, és b>d, ezért b>c

még megnézni ha a>c meg ilyenek

ezután, megnézni hogy 2x3nál, 3x2nél is ilyen-e, vagy valami. Szal ha kibővítjük sorral oszloppal.

Ezután már belátható hogy akármekkora mátrixoknál jó lesz ez.

aha, az igaz :) akkor az egyenlőségeket elhagyhatod, csak a biztonság kedvéért írtam oda őket.

De egyébként lehet <= a számok között, hiszen 1<=2 (kisebb, vagy egyenlő), nem borul ezzel semmi :) de tényleg elég a < is.

ez a bizonyítás valóban nem gimis anyag, de azért viszonylag egyszerű :) a problémaredukció sokmindenre jó.

esetleg megpróbálhatsz felírni 50 összekevert számot, a megadott alakban, és azokat a szabályok szerint rendezni, és megfigyelni a lépések hatásait, hátha szép magyar nyelven is meg lehet fogalmazni, hogy miért marad növekvő a számok sorrendje.