|
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. A 60. Nemzetközi Matematikai Diákolimpia 5. feladata ([1]) így szólt:
Bath Bankja érméket bocsát ki, melyeknek egyik oldalán , másik oldalán betű látható. Harrynek ilyen érméje van, amelyek előtte balról jobbra, egy sorban vannak elrendezve. Harry ismételten végrehajtja a következő műveletet: ha pontosan olyan érme van, amin van felül, akkor megfordítja a balról -adik érmét; máskülönben minden érmén van felül, és ekkor Harry megáll. Például esetén a sorozatból indulva a lépések sorozata, ami három lépés után megáll.
Bizonyítsuk be, hogy bármi legyen is a kiindulási sorozat, Harry véges sok lépés után megáll.
Minden kiindulási sorozatra jelölje azt a lépésszámot, ahány lépés után Harry megáll. Például és . Határozzuk meg átlagos értékét, amint végigfut a lehetséges kiinduló sorozaton.
A Középiskolai Matematikai és Fizikai Lapok 2019. novemberi számában megjelent a feladat egy lehetséges megoldása ([2]). Ebben a cikkben megadunk egy másik (talán egyszerűbb) megoldást és továbbgondoljuk a feladatot.
Az részt bizonyítsuk teljes indukcióval. érme esetén az állítás könnyen ellenőrizhető a kevés lehetséges eset végigvizsgálásával. Tegyük fel, hogy -ig igaz az állítás, tekintsük az érme esetét. Három esetre bontjuk a feladatot.
| 1. | Ha az utolsó, -edik érmén T látható (ez az esetek felében fordul elő), akkor azt az érmét sosem fogjuk megfordítani, hiszen ahhoz az kellene, hogy az összes érmén a H legyen látható. Így az első érmére alkalmazva az indukciós feltevést beláttuk ezt az esetet. |
| 2. | Ha az utolsó érmén H, az elsőn pedig T van. Ekkor, ha csak az utolsó érmén van H, (a művelet szerint) sorrendben az elsőtől az -edik érmet megfordítva mindenütt H lesz felül, és végül az -ediktől az elsőig haladva mindegyiket átfordítjuk T-re. Egyébként a megadott művelet szerint mindaddig, amíg az első érmén T és az -edik érmén H van csak a másodiktól az -edik érméket forgathatjuk, méghozzá pontosan úgy, mintha az első és az -edik elem ott sem lenne. Alkalmazva az indukciós feltevést -re elérhetjük, hogy a másodiktól az -edik érméig mindegyiken T látsszon. Ezután a már leírtak szerint járunk el, és végül mindegyik érmét átfordítjuk T-re, amivel beláttuk ezt az esetet is. |
| 3. | Ha utolsó és az első érmén H van, akkor a megadott művelet szerint mindaddig, amíg az első érmén H van csak a másodiktól az -edik érméket forgathatjuk, méghozzá pontosan úgy, mintha az első elem ott sem lenne. Alkalmazva az indukciós feltevést -re elérhetjük, hogy a másodiktól az -edik érméig mindegyiken T látsszon, majd az első érmét megfordítva befejeztük az indukciós bizonyítást. |
Az a jó ebben a bizonyításban, hogy a részre is ad egy rekurzív képletet. Jelöljük elem esetén -nel az átlagos lépésszámot. A fenti 1. pont -hez -el járul hozzá, hiszen az esetek felében fordul az elő. Hasonlóan, a 2. pont -et ad -hez, hiszen az az esetek negyedrészében fordul elő, első lépésként a ,,középső'' elemet kell T-re fordítani, és utána további lépés kell a feladat befejezéséhez. A 3. pont egy kicsit trükkösebb: az is az esetek negyedrészében fordul elő, de ott a második elemtől kell mindent T-re fordítani úgy, hogy tudjuk, hogy az utolsó elem H. Az összes lehetséges esetben szükséges lépések száma ebben az esetben , hiszen ,,megszorítások'' nélkül lenne lépés, de ebből ki kell vonni azon lépések számát (), amikor az utolsó elem T. Ez alapján a 3. pont hozzájárulása -hez | |
Így a következő rekurzív képletet kapjuk: | |
Kiindulva akár az értékből kapjuk, hogy amivel a feladatot megoldottuk.
Bár a rész egy érdekes kérdést vet fel, mégis természetesebb lenne azt kérdezni, hogy maximum hány lépésen belül fejeződik be a művelet. Persze attól, hogy ez természetesebb kérdés, nem lesz feltétlenül egyszerűbb, mint ahogy ebben az esetben sem az. Egy felső becslést könnyen tudunk adni a fentiek alapján: a 2. pontbeli eljáráshoz szükséges a legtöbb ,,extra'' lépés, miután befejeztük a többi elem megfelelő oldalra fordítását. Eszerint ha -nel jelöljük az elem esetén szükséges lépések maximális számát, akkor kapjuk az egyenlőtlenséget, amiből a fentiekhez hasonlóan -ból kiindulva nyerhetjük az becslést. De ha akár csak -re ellenőrizzük a négy lehetséges esetet, már ott sem érhető el a 4 lépéses maximum. Márcsak azért sem, mert a fentiek alapján mindenképpen véget ér az eljárás, így az eljárás során érmék állásai nem ismétlődhetnek, és a 4 lehetséges állás között maximum 3 átmenet/lépés lehet. Elméleti úton is viszonylag könnyen belátható, hogy a felső becslés nem lehet szigorú -re, hiszen a 2. pont csak akkor működik, ha az utolsó elem H, a rekurzió miatt az előtte lévő elemnek is H-nak kell lennie, és így tovább, vagyis az összes elem H lenne, azzal viszont lépésben végez az eljárás.
Ahogy a jól ismert mondás tartja: ,,a probléma félig meg van oldva, ha tudjuk, hogy mi a probléma''. Próbáljunk meg tehát sejtést szerezni a maximális lépésszámra. Leghatékonyabb, ha erre programot írunk, hiszen már érmére is elég hosszadalmas végigszámolni a 32 esetet. A következő eredményt kapjuk:
A minta könnyen felismerhető: az első ( egészrész) érmén T van felül, a többin H. A maximális lépésszámot sem nehéz kitalálni: az egymás utáni számok különbségei a természetes számokat adják, ami alapján lenne. Ez a probléma, ezt kellene belátni.
Nézzük meg pontosan, hogyan is működik az eljárás. Minden érme megfordításával eggyel nő vagy csökken a H-k száma, így a következő lépésben az eggyel jobbra (nőtt) vagy eggyel balra (csökkent) levő érmét fogjuk megfordítani. Vagyis amíg T-ket találunk, addig H-kat hagyunk magunk mögött és jobbra lépünk, akkor ,,fordulunk vissza'', amikor H-t találunk. Hasonlóan: amíg H-kat találunk, addig T-ket hagyunk magunk mögött és balra lépünk, akkor fordulunk vissza, amikor T-t találunk (vagy megállunk, ha nem találunk T-t). Ebből elég világos módon kirajzolódik egy balra-jobbra (vagy jobbra-balra) söprés jellegű művelet, amelyik minden irányban mindig legalább eggyel túllép az addig végigsöpört területen és jobbra haladva H-kat, balra haladva T-ket hagy maga mögött. Mennyi lehet akkor a maximális lépésszám? Visszafelé haladva az utolsó maximum lépés hagyhat T-t maga mögött balra lépve, előtte lépés jobbra, azelőtt lépés balra stb. Ezzel beláttuk, hogy a maximális lépésszám legfeljebb lehet. Ahhoz, hogy ez a maximális lépésszám előállhasson az kell, hogy
| 1. | ténylegesen minden irányú söprésnél (kivéve az utolsó) legyen egy ,,visszafordító érme'' és hogy |
| 2. | minden visszafordulásnál pontosan eggyel több lépést tegyünk meg, mint az előző, ellentétes söprési iránynál. |
Balra menve a T fordít vissza, jobbra menve pedig a H, és a balra illetve jobbra söprések száma legfeljebb eggyel térhet el egymástól. Ez megmagyarázza a fenti mintákat is, amelyekben a bal oldalon vannak a T-k, a jobb oldalon a H-k, és ezek száma legfeljebb eggyel tér el. Direkt módon is könnyen ellenőrizhető, hogy ezek a minták jó példát, sőt, minden -re az egyetlen lehetséges példát adják a maximális lépésszámra.
Érdekes, hogy a maximális és minimális (0) lépésszám átlaga éppen az átlagos lépésszám. Nézzük meg, hogy hány példa van a lehetséges lépésszámokra. Ha már úgyis programot írtunk a problémára, akkor ez sem okoz semmi nehézséget:
Ez alapján úgy tűnik, hogy a darabszámok szimmetrikusak az átlagos lépésszámra, ami megmagyarázná az átlagot a maximum alapján, vagy éppen fordítva, a maximumot az átlag alapján. Az a kérdés, hogy be tudjuk-e látni ezt a szimmetriát.
Legegyszerűbb lenne párbaállítani az érmék H ‐ T sorozatait úgy, hogy egy lépéses mintához egy lépéses minta tartozzon. Eszerint például esetén a TTTHHHH maximális lépésszámú mintához a TTTTTTT minimális lépésszámú minta tartozna. Hát, első ránézésre nagyon nem világos, hogy mi alapján rendelnénk egymáshoz pont ezt a két mintát. Közelítsük meg a problémát egy másik oldalról. Mik ezek a fenti táblázatban lévő számsorozatok? Szerencsére az interneten van segítség: az On-Line Encyclopedia of Integer Sequences ([3]). Abba beírva/bemásolva a hosszabb számsorozatokat (a rövidebbek túl sokféleképpen magyarázhatóak), a következő választ kapjuk például -re: A034140: Number of partitions of into distinct parts from ([4]). (Az eredeti szövegben levő -et -ra cseréltük, hogy ne keveredjen a cikkben használt jelöléssel, a a mi esetünkben a lépésszámot jelenti, tehát -tól -ig mehet.) Vagyis: hányféleképpen bontható a szám az számok ismétlés nélküli összegére. Hogy ennek mi köze a mi problémánkhoz? Egy kis utánagondolással ez világossá válik. A fenti jobbra-balra söprésnél a söprések hossza szigorúan növekszik (maximum lehet), tehát különbözö söpréshosszakat kapunk és azok összege adja ki a teljes lépésszámot. Vagyis a mi problémánk lefordítható a lépésszám különböző számok összegére bontásának feladatára. De a dolog fordítva is működik: egy adott számösszeghez tartozik egy megfelelő H ‐ T sorozat, amit a következő módon konstruálhatunk meg. Rendezzük az összeadott számokat csökkenő sorrendbe és hajtsuk végre a műveletünket a számoknak megfelelően fordítva. Ez azt jelenti, hogy a csupa T állásból és az első pozícióból kiindulva jobbra haladva a legnagyobb szám darabszámú érmét H-ra fordítunk, a visszafordító érmét úgy hagyva balra haladva a második szám darabszámú érmét visszafordítjuk T-re stb. Talán egy példán legegyszerűbb bemutatni az eljárást. Legyen , , ekkor az egyes számok alapján kialakuló H ‐ T sorozatok a következők lesznek (pirossal a változtatott érméket, kékkel az úgy hagyott, visszafordító érméket jelöljük):
Eszerint van egy kölcsönösen egyértelmű megfeleltetésünk a H ‐ T sorozatok és az számhalmaz részhalmazai között (ez utóbbiak felelnek meg az számok ismétlés nélküli összegeinek). Most már a párbaállítás könnyen kitalálható: egy adott halmazhoz tartozzon az halmaz, az komplementere. Egyrészt ez tényleg párokat ad: a komplementer komplementere az eredeti halmaz. Másrészt megfelelő párokat ad: ha az halmazban a számok összege , akkor az halmazban a számok összege azon számok összege lesz, amelyek nincsenek benne -ban, vagyis a halmazbeli számok összege mínusz , és pontosan erre volt szükségünk. A fenti példánknál esetén a TTTHHHH maximális lépésszámú mintához az halmaz tartozik, ennek komplementere az üres halmaz, ami valóban a TTTTTTT minimális lépésszámú mintának felel meg.
| SZTE, TTIK, Bolyai Intézet |
| E-mail: makayg@math.u-szeged.hu |
Ezt a kutatást a TKP2021-NVA-09 projekt támogatta. A TKP2021-NVA-09 számú projekt a Magyar Innovációs és Technológiai Minisztérium támogatásával valósult meg a Nemzeti Kutatási, Fejlesztési és Innovációs Alapból, a TKP2021-NVA támogatási konstrukció keretében. |
PDF | MathML 