Feladat: 1108. matematika gyakorlat Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Csóka Ezsébet ,  Goda Béla ,  Gróf P. ,  Gulyás A. ,  Hárs L. ,  Jakál L. ,  Jankó B. ,  Kardos János ,  Kiss Péter ,  Kmethy Gy. ,  Lőrincz A. ,  Magyar Á. ,  Molnár László ,  Müller Zója ,  Nagy Dénes ,  Pataki János ,  Sághy A. ,  Schván P. ,  Soós Miklós ,  Tél T. ,  Várhegyi Éva 
Füzet: 1968/február, 61 - 63. oldal  PDF  |  MathML 
Témakör(ök): Konstruktív megoldási módszer, Permutációk, Gyakorlat
Hivatkozás(ok):Feladatok: 1967/február: 1108. 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. Feladataink csak abban térnek el a 965. gyakorlatban * végzett átrendezésektől, hogy szövegeinket (egy sor helyett) kör kerületére írjuk. Így a szöveg első és utolsó betűje szomszédos, tulajdonképpen nincs kijelölt kezdőpont, továbbá egy betű egy másik helyre két irányban vihető át, végül a két szöveg a kör kerületére megegyező vagy ellentétes irányban írható fel (más szóval aszerint, hogy a betűk felső része a kör kerülete vagy középpontja felé van fordítva). Szövegeink 12-betűsek, így az átrendezett szöveg az eredetihez képest, a kezdő betű és az irány figyelembevételével, 24 különböző helyzetben állhat. Minden ilyen helyzetben ‐ a 965. gyakorlat I. megoldásának eljárását kissé módosítva ‐ megállapíthatjuk a szükséges cserék számát, végül kiválaszthatjuk azt a helyzetet, amely a legkevesebb (szomszédos) cserét igényli (vagy azokat a helyzeteket).

 

 

1. ábra
 

Írjuk egy szabályos 12-szög egymás utáni csúcsaihoz az AZ ORSZÁG HÁZA szöveg betűit, a betűk felső részét kifelé állítva, továbbá egy valamivel kisebb oldalú szabályos 12-szög-lemez csúcsaihoz a SÁRGA AZ HOZZÁ szöveg betűit ugyanolyan állásban (ugyanazon menetirányban). Helyezzük a lemezt a nagyobb sokszögre úgy, hogy középpontjuk egybeessék, és a belső szöveg 1. betűje (nevezzük ezt indexnek) a külső szöveg 6. betűjével (az ORSZÁG Z-jével) álljon együtt. Ezen a helyzeten mutatjuk meg a szükséges cserék számának megállapítását, mert ‐ mint a további 23 helyzet hasonló vizsgálata mutatja ‐ minden más helyzetben több csere szükséges, mint itt.
A belső betűket fogjuk cserélni, hogy a külső szöveget kapjuk. (Egyébként nyilvánvaló, hogy a fordított feladat ugyanannyi cserét igényel, vagyis ‐ ha ügyesen dolgoznak ‐ mind a két versenyző ugyanannyi cserével oldja meg a maga feladatát.) A csak egyszer szereplő G, H, O, R, S betűk új helyzete egyértelmű. Pl. a belső G-t 1 betűvel kell elfordítanunk a pozitív forgási irányban, ezt jelzi röviden a melléje írt +1, hasonlóan írtuk a belső H, O, R, S mellé a +4, -1, +4, +1 számot. Nyilvánvaló az is, hogy a mindkét szövegben egymás mellett álló A, A betűk belső példányaihoz -2, -2 írandó. Nem célszerű a 7. helyen álló Á betűt a helyén hagyni, mert így a másik Á-t vagy +7 elfordítás vinné a 10. helyre, vagy -5, az utóbbi esetben átlépné és 1-gyel visszavetné a 7. helyen állót, tehát a két Á helyre juttatása 6 cserét igényelne. Ezért azt tervezzük, hogy a 7. helyen álló Á-t ‐ 3-mal visszük a 10. helyre és az 5. helyen állót -2-vel a 7. helyre, ez csak 5 csere. Végül a három Z-betű mozgatásának megtervezésében az ígér legkevesebb cserét, ha a 3. helyen állót a 2.-ra visszük, a 4. helyen állót a 6.-ra és a 12. helyen állót a 11.-re (+1, ill. -2, ill. +1).
Tervünk mindegyik elemében csak egyféle betűt tekintettünk. Egy csere viszont két betűt mozdít el egymással ellentétes irányban, ezért a különböző igények összeegyeztetésére lehet szükség. Esetünkben a beírt pozitív, negatív számok összege -12, ill. -12, így nincs szükség változtatásra, mert így az igények várhatóan kiegyenlítik egymást. Pl. a 2. és 3. helyen álló O, Z cseréje az elfordítások szükséges számát -1, +1-ről 0, 0-ra változtatja. (Más helyzetben viszont szükség lehet arra, hogy pl. +5 helyett -7-et írjunk, így érjük csak el a mostani helyzetet; egy 6-os elfordításhoz pedig eredetileg nem is írhatunk előjelet.)
A cserék végrehajtásában elsősorban olyan szomszédokat cserélünk, amelyek elfordítási igényét ellentett jelű számok fejezik ki, és éppen egymás felé kell mozdulniuk, mint a fenti OZ példájában. Eszerint 12-nél kevesebb cserével semmi esetre sem érünk célt. Természetesen nem cserélünk fel két szomszédos és egyenlő jelű igényszámmal bíró számot, ha a kívánt közös menetirányukban elöl a nagyobb abszolút értékű szám áll (pl. a 8. és a 9. helyen). Ennek a fordított esetében viszont szükséges a csere ‐ ezt neveztük a 965. gyakorlatban előzésnek ‐, és ekkor a megelőzött betű igénye abszolút értékben 1-gyel nő. Ilyen a 12. és 1. helyen álló Z, H betűpár esete, és előre látható, hogy ilyenné válik R és S kölcsönös helyzete az R, Á csere után. Több előzés nem lesz, a szükséges cserék száma legalább 14.
Tovább emelkedhetne a szükséges cserék száma a helyükön maradó (0-igényű) betűk miatt is, ha egy másik betűt kell átvinnünk a helyükön, s emiatt ki kell mozdulniuk, az ellenkező irányban. Ábránk indulási állásában nincs ilyen helyzet, de ilyen alakulna, ha a 10., 11., 12. és 1. helyek négy betűje közti cseréket a 11. és 12. helyen álló A, Z-vel kezdenők, mert Z-n a két A kívánna átlépni. Azonban a Z, H előzéssel kezdve a cseréket, Z további cseréi mindkét betűre előnyösek. ‐ Ugyanez a helyzet az R, Á csere után a 4‐7. helyeken. Példánk valóban 14 cserével átrendezhető.
Hasonlóan kapjuk, hogy minden más kiinduló állásból legalább 15 csere szükséges. 15 cserére vezető induló helyzet az, ha a belső szöveg betűinek felső része befelé áll ‐ a szöveg az órajárással szemben olvasandó ‐ és az index a külső szöveg 7. helyén áll. ‐ Megjegyezzük azonban, hogy a tervezés és csereszámlálás célszerűbben végezhető egymás utáni egyenes sorokban, az indexállást 1-gyel -1-gyel változtatva; így ugyanis az egyértelműen adódó betűk csereigénye mindenesetre gépiesen beírható, esetleg még a többszörös betűké is.
 

 

2. ábra
 

II. A második cseremód vizsgálati módszerét is a legkevesebb cserét igénylő helyzet esetében mutatjuk be. Írjuk a ,,SÁRGA...'' szöveg betűit fejjel befelé, a 11. helyen álló indextől kezdve. Ekkor a 2., 3., 8. és 10. helyen már a kívánt betű áll (legfeljebb belülről kifelé fordítandó a betű, ezt nem tekintjük cserének). A további 8 betű pedig 4 olyan párba rendezhető, hogy mindegyik pár tagjai egymás helyén éppen célban vannak; ezek az 1. és 6. helyen álló Z, A, a 4. és 9. helyen álló H, R, az 5. és 11. helyen álló Z, S, végül a 7. és 12. helyen álló A, Á pár. Ebből az állásból 4 csere elég az átrendezéshez. Minden más helyzetből legalább 5 csere szükséges. Pl. a 8. helyre téve az indexet és a külsővel azonos állásban írva a belső szöveget, A, A, Á, Z, Z már a helyén van, a többi betűk azonban egy 3- és egy 4-tagú ciklust alkotnak: (S, Z, G) és (O, H, Á, R), így a szükséges cserék száma (3-1)+(4-1)=5.
 

  Goda Béla (Győr, Czuczor G. Bencés g., II. o. t.)
  Kardos János (Budapest, Kölcsey F. g. II. o. t.)
  Soós Miklós (Budapest, Fazekas M. gyak. g. II. o. t.)
 

Megjegyzés. Számos versenyzőt tévesztett meg a II. cseremód esetében az utoljára mondott példa; úgyszintén az I. cseremód esetében is ebből a helyzetből indultak és 18-at véltek minimális csereszámnak.
* Lásd a megoldást K. M. L. 33 (1966. nov. ) 135. o.