|
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ő É É 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ó É-jét a KÉRI szóba ‐, így ugyanis elkerüljük É és É 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. ) 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 .
Ennyi csere akkor lenne elegendő, ha miden cserében mindkét betű a véghelyzete felé mozdulna el, mint pl. az eredeti sorrendben és cseréjében. Egyes cserék azonban csak az egyik betűt viszik véghelyzete felé. Pl. és az átrendezés folyamán valamikor egyszer cserélnek, mert -nek meg kell előznie a szintén jobb felé tolódó -et, emiatt ú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 -szor cserél, vagy az . és . hely között -szer), és a cserék száma -gyel nő. Hasonlóan az jelű betűknek is kell cserélniük a helyükön áthaladó betűk miatt, pl. helyén áthalad és , az először való áthaladás egy új nyilat hoz létre részére. -t és -t jobbra haladásukban ‐ betű előzi: és (szemléletesen mondva azért, mert az utóbbiak nyila lefedi amazokét és a nyilak iránya megegyező), ezt jelöltük a és nyila kezdőpontjához írt -essel. Ugyanígy -et is betű előzi bal felé, az , , , É, és É betűket pedig ‐, ezért az előzések miatti többlet-cserék száma . Az -jelű betűkön áthaladó , , , ill. betűpár miatt pedig -zel nő a cserék száma (, ill. valamelyik irányú nyíl fedi le e négy betű -hosszúságú nyilát). Mindezt egybevetve a szükséges cserék száma . 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 É-t és -t is a helyükön hagyjuk (hiszen megfelelő helyen állnak) és É-et visszük helyére, -at helyére (lásd a táblázat alsó sorát), így 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: és , valamint és között, de minden más csere legfeljebb az egyik betűt viszi céljába, pl. az helyére törekszik, -nek azonban nem helyére kell jutnia. Mégis célszerű a , csere, mert utána az , csere már mindkét betűt helyére juttatja; így , , ciklikusan (körben) egymás helyére léptek páros cserében. Hasonlóan rendezhető a szintén -tagú , É, és a -tagú , , , Á, , ciklus, az utóbbi megengedett cserével, pl. egymás után átadja mindenkori helyét a , , A', , betűnek, végül az ötödik cserében maga is az előírt helyre jut (ezért kisebb -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 ‐ taggal) ciklusban cserével hajtottuk végre.
Megjegyzés. Megmutatjuk, hogy a II. csere-mód esetében -nél kevesebb cserével nem érhetünk célt. Támaszkodunk arra, hogy az átrendezés terveként 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 ciklust létrehozni. (Ahogyan az (, ) két-elemű ciklusban a csere az (), () 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 (, , ) ciklus utolsó, betűjét cseréltük fel egy (, , ) ciklus első, betűjével ( is, is lehet ). 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 , illetőleg esetén ahhoz hozzácsatoltuk. Valóban, azon a helyen, ahová -et vinnünk kell, most áll, viszont mostani helyére -et kell juttatnunk, az új ciklus: (, , , , , , , ). Ez esetén is érvényes, meggondolva, hogy ekkor az előtti elem önmaga. Ha viszont ugyanazon ciklus két betűjét cseréljük fel, pl. az (, , , ) ciklusban -et -vel (), e csere után a betűk ciklust alkotnak -től -ig és -től -ig, mert ahova -et vinnünk kell, ott most áll, és ahová -t kell vinnünk, ott ( és 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 -gyel csökkenti, vagy -gyel növeli a ciklusok számát. A ciklusból ( helyben maradó betű és több elemű ciklus) -nél kevesebb cserével nem lehet 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: | | (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ő -nek valamikor cserélnie kell az eredeti sorrendben előtte álló betű mindegyikével; a . helyre viendő -nak szintén az előtte volt betűvel, kivéve a -iket, ami most is előtte áll; a . helyre (a . helyről) viendő betűnek az előtte volt betű közül -vel nem kell cserélnie, így cserét kell végeznie s i. t. Más szóval: -nek , -nek , -nek 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
(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 -et, -et, -t s i. t. visszük új helyére, akkor 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.)
|
|