Kezdőlap


Feladat:	Gy.2760	Korcsoport: 14-15	Nehézségi fok: átlagos
Megoldó(k):	Katona Zsolt , Tarján Dénes
Füzet:	1992/október, 309 - 310. oldal		PDF \| MathML
Témakör(ök):	Számelrendezések, Gyakorlat
Hivatkozás(ok):	Feladatok: 1992/március: Gy.2760

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 $a, b$ párt, amelyre $a$ megelőzi $b$ -t és $a > b$ , majd $a$ -t és $b$ -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 $i$ -edik sorának elemei $a_{1}$ és $b_{1}$ , $j$ -edik sorának elemei $a_{2}$ és $b_{2}$ , továbbá $a_{1} \leq b_{1}, a_{2} \leq b_{2}$ és $i < j$ .

1. eset:

a_{1} \leq a_{2}

és

b_{1} \leq b_{2}

; ekkor az

i

-edik és

j

-edik sort változatlanul hagyjuk.

2. eset:

a_{1} \leq a_{2}

és

b_{1} > b_{2}

. A második oszlopban kicseréljük egymással a

b_{1}, b_{2}

számokat. Az így kapott új

i

-edik sorra

a_{1} \leq a_{2} \leq b_{2}

, az új

j

-edik sorra

a_{2} \leq b_{2} < b_{1}

3. eset:

a_{1} > a_{2}

és

b_{1} \leq b_{2}

. Az első oszlopban

a_{1}

-et és

a_{2}

-t felcserélve, az új sorokban

a_{2} < a_{1} \leq b_{1},

a_{1} \leq b_{1} \leq b_{2} .

4. eset:

a_{1} > a_{2}

és

b_{1} > b_{2}

. Ezúttal

a_{1}

-et

a_{2}

-vel is és

b_{1}

-et

b_{2}

-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

{a

b}

-t rossz számpárnak, ha

a

megelőzi

b

-t és

a > b

. Megmutatjuk, hogy

a

-t és

b

-t felcserélve a rossz párok száma legalább

1

-gyel csökken. Nyilván

{a

b}

megszűnik rossz párnak lenni. A további párok közül elegendő az

{a

x}

és az

{y

b}

alakúakat vizsgálni, ahol

x

, ill.

y

az eredeti sorban

a

és

b

között helyezkedik el. Ha a csere előtt

{a

x}

nem volt rossz, azaz

a < x

, akkor

b < a

a miatt

{b

x}

sem lesz rossz pár a csere után. Hasonló a helyzet az

{y

b} \mapsto {y

a}

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