Feladat: 965. matematika gyakorlat Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Babai L. ,  Eszes G. ,  Hegedüs A. ,  Kovács Miklós ,  Lelkes A. ,  Naszódi M. ,  Pap Márta ,  Pethő I. ,  Semsey A. ,  Sipos L. ,  Szentgáli Á. ,  Szentpéteri Kamilla ,  Szikora József ,  Takács L. ,  Tamási P. 
Füzet: 1966/november, 135 - 138. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorikai leszámolási problémák, Gyakorlat, Logikai feladatok
Hivatkozás(ok):Feladatok: 1965/február: 965. matematika gyakorlat

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.

I. megoldás. I. Az első cseremód esetében a többször előforduló betűkkel nyilvánvalóan akkor végzünk kevesebb cserét, ha egymás közti sorrendjüket változatlanul hagyjuk, vagyis pl. a régi szöveg első É É1 betűjét az új szöveg első É-jébe, a TAKARÉK szóból a PÉNZT szóba visszük ‐ ennélfogva a PÉNZTÁR szó É2-jét a KÉRI szóba ‐, így ugyanis elkerüljük É1 és É2 fölösleges cseréjét. Eszerint minden egyes betű új helyzete egyértelműen meg van határozva. A táblázaton a betűk elmozdulásait egy-egy nyíl szemlélteti, a helyben maradó betűket pedig (pl. P) × jelöli. Minden betű legalább annyi cserében vesz részt, ahányszor a hozzá tartozó nyíl átmetsz egy-egy betűközt jelölő függőleges vonalat. Az átlépések összes számát ilyen vonalanként csoportosítva is megállapíthatjuk, evégett írtuk be mindegyikre lent az egy irányban átmetsző nyilak számát, pl. az 5. és 6. hely közti vonalra 5-öt (ez a szám mindkét irányban nyilvánvalóan ugyanaz). E számok összege 63.

 
 

Ennyi csere akkor lenne elegendő, ha miden cserében mindkét betű a véghelyzete felé mozdulna el, mint pl. az eredeti sorrendben I és T1 cseréjében. Egyes cserék azonban csak az egyik betűt viszik véghelyzete felé. Pl. M és E1 az átrendezés folyamán valamikor egyszer cserélnek, mert M-nek meg kell előznie a szintén jobb felé tolódó E1-et, emiatt E1 útja egy balra és egy jobbra lépéssel bővül (a cserék egymásutánja szerint vagy valamelyik betűköz fölött 3-szor cserél, vagy az 1. és 2. hely között 2-szer), és a cserék száma 1-gyel nő. Hasonlóan az × jelű betűknek is kell cserélniük a helyükön áthaladó betűk miatt, pl. R3 helyén áthalad I és T3, az először való áthaladás egy új nyilat hoz létre R3 részére.
G-t és Y-t jobbra haladásukban 22 betű előzi: M és E1 (szemléletesen mondva azért, mert az utóbbiak nyila lefedi amazokét és a nyilak iránya megegyező), ezt jelöltük a G és Y nyila kezdőpontjához írt 2-essel. Ugyanígy R1-et is 2 betű előzi bal felé, az E1, K1, A2, É1, K2 és É2 betűket pedig 11, ezért az előzések miatti többlet-cserék száma 12. Az ×-jelű betűkön áthaladó 3, 3, 3, ill. 1 betűpár miatt pedig 10-zel nő a cserék száma (3, ill. 1 valamelyik irányú nyíl fedi le e négy betű 0-hosszúságú nyilát). Mindezt egybevetve a szükséges cserék száma 63+12+10=85.
Az átrendezés végrehajtásában csak olyan cserét végezzünk, mely legalább az egyik cserélt betűt előírt új helye felé mozdítja el.
 

II. A második átrendezési mód esetében nyilvánvalóan célszerűbb, ha É2-t és T2-t is a helyükön hagyjuk (hiszen megfelelő helyen állnak) és É1-et visszük R2 helyére, T3-at G helyére (lásd a táblázat alsó sorát), így 16 betűt kell megengedett cserékkel előírt helyükre juttatnunk.
Most is van mindkét cserélt betű részére előnyös csere: A1 és E1, valamint R1 és E2 között, de minden más csere legfeljebb az egyik betűt viszi céljába, pl. G az I helyére törekszik, I-nek azonban nem G helyére kell jutnia. Mégis célszerű a G, I csere, mert utána az I, T3 csere már mindkét betűt helyére juttatja; így G, I, T3 ciklikusan (körben) egymás helyére léptek 2 páros cserében. Hasonlóan rendezhető a szintén 3-tagú K1, É1, R2 és a 6-tagú M, A2, K2, Á, Y, T1 ciklus, az utóbbi 5 megengedett cserével, pl. M egymás után átadja mindenkori helyét a T1, Y, A', K2, A2 betűnek, végül az ötödik cserében maga is az előírt helyre jut (ezért kisebb 1-gyel a cserék száma a ciklus tagjainak számánál).
Így az átrendezést (az elsőnek említett két cserét is ciklusnak tekintve 22 taggal) 5 ciklusban 1+1+2+2+5=11 cserével hajtottuk végre.
 

Megjegyzés. Megmutatjuk, hogy a II. csere-mód esetében 11-nél kevesebb cserével nem érhetünk célt. Támaszkodunk arra, hogy az átrendezés terveként 22 betűnkből több-kevesebb betűből álló ciklusokat írtunk fel, minden betű után azt a másik betűt írva, amelynek helyére ezt vinnünk kell, és minden ciklust az után a betű után lezárva, amelyet a ciklus első betűje helyére kell vinnünk. Minden már az előírt helyén álló betűt is egy-elemű ciklusnak tekintünk. Ekkor a cél: minél kevesebb cserével 22 ciklust létrehozni. (Ahogyan az (A1, E1) két-elemű ciklusban a csere az (A1), (E1) egy-elemű ciklusokat hozta létre.)
 
 

Nézzük, milyen változást okoz két tetszés szerinti betű cseréje a ciklusok számában. Vagy két ciklus egy-egy elemét cseréljük fel, vagy egy ciklus két elemét. Mivel egy ciklus felírását bármelyik elemén kezdhetjük, feltehetjük az első esetben, hogy egy (a1, ..., ak) ciklus utolsó, ak betűjét cseréltük fel egy (b1, ..., bm) ciklus első, b1 betűjével (k is, m is lehet 1). Ezzel a két ciklust eggyé alakítottuk, a második ciklust a maga egészében beiktattuk az első ciklus utolsó két eleme közé, ha k>1, illetőleg k=1 esetén ahhoz hozzácsatoltuk. Valóban, azon a helyen, ahová ak-1-et vinnünk kell, most b1 áll, viszont ak mostani helyére bm-et kell juttatnunk, az új ciklus: (a1, ..., ak-1, b1, b2, ..., bm, ak). Ez k=1 esetén is érvényes, meggondolva, hogy ekkor az ak előtti elem önmaga.
Ha viszont ugyanazon ciklus két betűjét cseréljük fel, pl. az (a1, a2, ..., ak) ciklusban a1-et aj-vel (j>1), e csere után a betűk 2 ciklust alkotnak a1-től aj-1-ig és aj-től ak-ig, mert ahova aj-1-et vinnünk kell, ott most a1 áll, és ahová ak-t kell vinnünk, ott aj (j=2 és j=k esetén két szomszédos elemet cserélünk fel, a hátrább állott elem a részére előírt helyre jut).
 
 

Ezek szerint egy csere vagy 1-gyel csökkenti, vagy 1-gyel növeli a ciklusok számát. A 11 ciklusból (6 helyben maradó betű és 5 több elemű ciklus) 11-nél kevesebb cserével nem lehet 22 ciklust alakítani. Az átrendezés megvalósításához bármely olyan csere megfelelő, amelyben a cserélt betűk ‐ a rendezés pillanatnyi helyzetében ‐ ugyanegy ciklushoz tartoznak.
 
II. megoldás a feladat I. részéhez. A betűknek az I. megoldásban megállapított új sorrendbe állítását úgy is kimondhatjuk, hogy az egymás utáni helyekre rendre az első sorrend következő sorszámú helyén álló betűt kell vinni szomszédos cserékkel:
7,8,18,19,11;3,4,2,20,1;5,9,10,14,12;16,17,22,13,15;21,6.(1)

A cserék számának alábbi megállapításában minden cserét csak az egyik betűjéhez tartozónak tekintünk, éspedig ahhoz, amelyiknek az eredeti sorrendben nagyobb volt a sorszáma. Eszerint az első helyre viendő T-nek valamikor cserélnie kell az eredeti sorrendben előtte álló 7-1=6 betű mindegyikével; a 2. helyre viendő A-nak szintén az előtte volt 8-1=7 betűvel, kivéve a 7-iket, ami most is előtte áll; a 3. helyre (a 18. helyről) viendő betűnek az előtte volt 17 betű közül 2-vel nem kell cserélnie, így 15 cserét kell végeznie s i. t.
Más szóval: T1-nek 6, A1-nek 6, T2-nek 15 olyan betű került mögéje s i. t., melynek eredeti sorszáma kisebb az övénél. Így haladva végig (1)-en, a cserék száma
(6+6+15+15+8)+(2+2+1+11+0)+(0+1+1+3+1)++(3+3+4+1+1)+1+0=85


(az összeadandókat ötösével zárójelbe foglaltuk).
Ezzel egyszersmind sorrendet is adtunk a cserék végrehajtására: ha egymás után T1-et, A1-et, T2-t s i. t. visszük új helyére, akkor 85 cserével valóban a kívánt sorrend áll elő.
 
Kovács Miklós (Budapest, Berzsenyi D. G.)

Szikora József (Pannonhalma, Bencés G.)