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. Véges sok szám növekvő sorba rendezése mindig megtehető a következő átalakítás véges sokszori alkalmazásával: a sorozatból tetszés szerint kiválasztunk egy olyan párt, amelyre megelőzi -t és , majd -t és -t felcseréljük. A feladat állítását nyilván elegendő két oszlopból álló táblázatra igazolnunk. Tegyük fel, hogy egy ilyen táblázat -edik sorának elemei és , -edik sorának elemei és , továbbá és . 1. eset: | és ; ekkor az -edik és -edik sort változatlanul hagyjuk. |
2. eset: | és . A második oszlopban kicseréljük egymással a számokat. Az így kapott új -edik sorra , az új -edik sorra . |
3. eset: | és . Az első oszlopban -et és -t felcserélve, az új sorokban |
4. eset: | és . Ezúttal -et -vel is és -et -vel is felcseréljük. |
Látható, hogy az 1., 2., 3., 4. típusú lépéseket elég sokszor végrehajtva, mindkét oszlopban növekvő sorban állnak a számok. Mivel egyik lépés sem rontja el a sorok megfelelő rendezettségét, a feladatot megoldottuk.
Megjegyzés. A megoldás elején ismertetett sorbarendezési módszer helyessége a következőképpen látható be. Nevezzük , -t rossz számpárnak, ha megelőzi -t és . Megmutatjuk, hogy -t és -t felcserélve a rossz párok száma legalább -gyel csökken. Nyilván , megszűnik rossz párnak lenni. A további párok közül elegendő az , és az , alakúakat vizsgálni, ahol , ill. az eredeti sorban és között helyezkedik el. Ha a csere előtt , nem volt rossz, azaz , akkor a miatt , sem lesz rossz pár a csere után. Hasonló a helyzet az , , párokkal is.
Tarján Dénes (Bp. Piarista Gimn., II. o. t,) és Katona Zsolt (Fazekas M. Főv. Gyak. Ált. Isk., 6. o. t.) dolgozata alapján
|