Cím:	Kombinatorikai problémák egy egyszemélyes játék kapcsán I.
Szerző(k):	Mészáros Gábor
Füzet:	2008/december, 514 - 520. oldal	PDF  |  MathML
Témakör(ök):	Szakmai cikkek

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. Bevezetés   Egy érdekes matematikai játék megalkotásához meglepően kevés segédeszköz is elégséges: néhány korong a sakktáblán, színezett pontok a síkon, egy gondolt szám, véletlenszerűen kisorsolt színes sapkák $\text{...}$ és némi ötlet; egy jól megválasztott szabályrendszer, egy-két frappáns kérdés és feladat. Jelen cikkben egy saját ötletből született, lényegében egyszemélyes játék, avagy feladvány néhány változatát szeretném bemutatni.   Feladványainkban számozott dobozok között ingázó golyók ,,táncát'' követjük nyomon, melyek előre meghatározott szabályrendszernek engedelmeskedve vándorolnak dobozról dobozra. Vizsgálódásunk tárgya elsősorban a vándorlások végessége, illetve, véges vándorlás esetén a vándorlás hosszának lehetséges maximuma. Feladványaink közös jellemzője, hogy az aktuális szabályrendszer keretein belül mi határozhatjuk meg a dobozokba helyezendő golyók kezdeti elrendezését, ezt követően pedig felkérünk valakit a közönség soraiból, hogy az így elkészített ,,játéktérben'' hajtsa végre az adott játékban előírt lépéseket. Célunk, hogy az ,,önként'' jelentkezőt minél tovább játékban tartsuk. Az alábbiakban bemutatásra kerülő változatokban ennek korlátait igyekszünk minél pontosabban megadni. Eredményeinket általában feladat formájában fogalmazzuk meg, ezzel is biztatva az olvasót, hogy a bizonyítások elolvasása előtt önállóan is próbálkozzon az állítások igazolásával.   Megjegyzés. Habár az alább közlésre kerülő kérdésfelvetések sajátosságuk következtében nehezen helyezhetőek el egy matematikai ág részterületeként, a bizonyítások során felhasznált technikák és megoldási módszerek gyakorta alkalmazott eszközei az úgynevezett ,,Keresési probléma'' fegyvertárának, melynek számtalan érdekes elméleti eredménye mellett gyakorlati felhasználhatósága is figyelemre méltó.   Az ,,egyszerű dobozos játék''   Az előttünk álló asztalon $k$ db $\left(k\ge 2\right)$, 1-től $k$-ig sorszámozott, kezdetben üres doboz található. A játék előkészületeként a dobozok közül néhányban (akár valamennyi dobozban) összesen $k$ db egyforma golyót helyezhetünk el, tetszőleges módon. Ezt követően játékosunk véletlenszerűen választ egy dobozt, és a következőket hajtja végre: $•$ Amennyiben a választott doboz nem tartalmaz golyót, vagy a dobozban található golyók száma megegyezik a doboz sorszámával, elégedetten hátradől, és befejezi a játékot. $•$ Az előzőtől eltérő esetben az $s$ sorszámú, $g$ golyót tartalmazó doboz valamennyi golyóját áthelyezi a $g$ sorszámú dobozba (ezt nevezzük lépésnek a játékban), és az iménti vizsgálódást elvégzi a $g$ sorszámú dobozon is. A fent leírtak alapján áldozatunk kizárólag akkor fejezheti be a pakolást, ha az eljárás valamelyik lépésében a kezében lévő golyókat üres dobozba helyezi. Nyilvánvalóan nem remélhetjük, hogy feladatunkkal sikerül a végtelenségig az asztalhoz láncolnunk őt, hiszen a játékban az egymást követő lépések során egyre több golyó gyűlik össze a kezében (illetve az aktuális dobozban, amelybe a golyókat helyezte), ezért a golyók kezdeti száma korlátot szab a lépésszámra. Az alábbiakban szeretnénk meghatározni az eljárás lépésszámának lehetséges maximumát.   1. feladat. Igazoljuk, hogy játékosunkat legfeljebb $k$ lépés megtételére kényszeríthetjük $k$ doboz (és golyó) esetén, és becslésünk éles, ez a lépésszám elérhető.   Állításunk könnyedén igazolható, hiszen előbbi, véges lépésszámot igazoló érvelésünket kell csupán tüzetesebben megvizsgálnunk. Utolsó lépésünktől eltekintve minden egyes lépés során a mozgatott golyók száma legalább eggyel nő; mivel ennek kezdeti értéke legalább 1, így értelemszerűen legfeljebb $k-1$ növelés, ezáltal ‐ utolsó lépésünket is beleszámolva ‐ legfeljebb $k$ lépés történhetett. Ezzel állításunk első felét igazoltuk. A kívánt lépésszám megvalósításához szükséges, hogy kezdetben választott dobozunk pontosan 1 golyót tartalmazzon, és ezt követő lépéseink során a mozgatott golyók száma egyesével növekedjen, összesen $k-1$ alkalommal. Valamennyi dobozba pontosan 1 golyót helyezve a fenti feltételek teljesülnek, amennyiben a játékos az első lépésben a $k$ sorszámú dobozt választja. Tehát, a fent megcélzott lépésszám elérhető, sőt, fenti megfontolásunk azt is igazolja, hogy a maximális lépésszám elérésére ettől eltérő konstrukció nincsen. Kiszemelt áldozatunkat tehát legfeljebb a dobozok számával megegyező számú lépés megtételére kényszeríthetjük. Megjegyzendő, hogy jelen feladatban helytelenül nevezzük fent leírt tevékenységünket ,,kényszerítésnek'', hiszen a ténylegesen megtett lépések száma nagyban függ a kezdő doboz választásától; elemzésünkben tehát mindössze azt vizsgáljuk, hogy egy megfelelően választott konstrukcióból ,,mi hozható ki'', ha a szerencse mellénk szegődik. Jelen játékunkban nem is várhatunk el olyan konstrukciót, amely tetszőleges kezdőlépés esetén legalább $j$ lépéses eljárást garantál ($j\ge 1$); tetszőleges elrendezés tartalmaz ugyanis üres, vagy sorszámával egyező számú golyót tartalmazó dobozt, ezt választva tehát az eljárás egyetlen lépés megtétele nélkül zárul le. Amennyiben kifejezett igényünk a játékostárs tartós lefoglalása, úgy ‐ feltételezve, hogy a dobozok, illetve golyók kezdeti száma már meghatározott ‐ a lépésszám növelésére az egyik legkézenfekvőbb lehetőség, ha a játékost a játék iterálására szólítjuk fel. Tehát az első doboz választását követő, legfeljebb $k$ lépéses golyópakolás után újabb doboz választására kötelezzük áldozatunkat, mellyel az ismert szabályok szerint köteles ismételni az eljárást. Az ismétlések számát tetszés szerint növelhetjük, remélve, hogy a többszörös iterálás hatására a lépésszám lehetséges maximumát is a dobozszám sokszorosára tudjuk növelni. Játékunk végállapotának értelemszerűen a golyók egy olyan elrendezését tekintjük, melyben minden doboz üres, vagy sorszámával megegyező számú golyót tartalmaz (végállapot elérésekor az eljárás befejeződik, függetlenül a megkövetelt ismétlések számától). A szemlélet azt sejteti, hogy az eljárás ismétlésekor az egyes ,,körök'' lépésszáma egyre kevesebb lesz, mivel a játéktér egyre rendezettebbé válik; egyelőre azonban még annak kérdése sem tisztázódott, igaz-e, hogy a játékost garantáltan legfeljebb véges számú iterálásra késztethetjük, azaz a játék véges sok lépésben leáll-e. Végeztessük ezért játékunkban az ismertetett eljárást a lehetőségek kimerítéséig (elfogadva az esetleges, nem véges lépésszámú pakolás lehetőségét is).   Az ,,ismétléses dobozos játék''   Nevezzük a továbbiakban azokat a dobozokat, amelyek sorszámuknak megfelelő számú golyót tartalmaznak, ,,rendesnek''. Az előttünk álló asztalon $k$ db $\left(k\ge 2\right)$, 1-től $k$-ig sorszámozott, kezdetben üres doboz található. A dobozok közül néhányban (akár valamennyi dobozban) összesen $k$ db, teljesen azonos golyót helyezhetünk el a korábban ismertetett módon. Ezt követően játékosunk a következőket hajtja végre: $•$ Amennyiben a golyók aktuális elrendezése végállapot, befejezi a játékot. $•$ Amennyiben az elrendezés nem végállapot, véletlenszerűen választ egyet a nem üres, és nem rendes dobozok közül (ezek elhelyezkedését minden egyes választás előtt közöljük a játékossal), a kiválasztott, $s$ sorszámú dobozban található $g$ golyót ($s\ne g$) áthelyezi a $g$ sorszámú dobozba, majd a $g$ dobozzal az ,,egyszerű dobozos játékban'' ismertetett műveleteket végzi. A megállást követően jelen eljárásunk lépéseit ismétli (a végtelenségig, vagy a végállapot eléréséig).   1. megjegyzés. Ebben a szabályrendszerben szükséges kikötnünk, hogy a játékos nem választhat üres, vagy rendes dobozt. Ennek elhagyásával ugyanis tetszőleges ‐ nem végállapotot tartalmazó ‐ konstrukció esetén eljárásunk a végtelenségig ismételhető: mivel tetszőleges elrendezés tartalmaz legalább egy üres, vagy rendes dobozt, az eljárás valamennyi lépésében ezen dobozok közül választva a végállapot nem érhető el. Célszerű ugyan ebben a játékban, hogy a lépésszám vizsgálatánál a doboz kiválasztását nem tekintjük külön lépésnek (a továbbiakban így járunk el), bajainkat azonban ez sem orvosolja, hiszen megtörténhet, hogy a játékos egyetlen lépést sem tesz meg, holott a kezdeti állapot nem végállapot.   2. feladat. Igazoljuk, hogy tetszőleges kezdőhelyzetből indítva az ,,ismétléses dobozos játékot'', annak lépésszáma véges. Adjunk minél jobb becslést a lépésszámra.   Az alábbiakban igazoljuk, hogy ‐ az előbb vizsgált megkötések után ‐ a játék tetszőleges kezdőállás és dobozválasztás esetén csak véges sokszor ismételhető, és a lépések száma $k$ doboz esetén legfeljebb $2\left(k-1\right)$ lehet. Ehhez elsőként az első feladatnak egy, a már ismertetettől eltérő megoldását közöljük.   Második megoldás az 1. feladatra: Az eredeti feladatot az üres dobozok számának változását figyelemmel kísérve oldjuk meg. Vegyük észre, hogy eljárásunk minden lépésében vagy üres dobozba érkezünk (ekkor értelemszerűen megállunk), vagy az üres dobozok száma eggyel nő (egy doboz tartalmát másik, nem üres dobozba helyeztük). Mivel kezdetben legalább 0 üres dobozunk volt, míg a végállapotban legfeljebb $k-1$ lehetett, az üres dobozok száma legfeljebb $k-1$ alkalommal nőhetett, így az előzőhöz hasonlatos módon az eljárás legfeljebb $k$ lépésben véget ér.   Az ,,ismétléses játék'' vizsgálata: Megoldásunkban az üres dobozok számának, illetve az üres és rendes dobozok együttes számának változását követjük nyomon a játék során. Kezdetben az üres dobozok száma az előzőekhez hasonlóan legalább 0, a végállapotban pedig legfeljebb $k-1$. Az üres és rendes dobozok együttes száma azonban kezdetben legalább 1 (ha ugyanis nincs üres doboz, akkor az összes dobozban ‐ így az 1-es sorszámúban is ‐ pontosan 1 golyó található), míg a végállapotban ez az érték legfeljebb $k$ lehet. Azt állítjuk, hogy a játék tetszőleges lépése során e két mennyiség egyike sem csökken, sőt, minden egyes lépésben legalább az egyik mennyiség nő. A megoldásban két esetet különböztetünk meg: $\left(i\right)$ Ha egy lépésben a $d_i$ dobozból a nem üres $d_j$ dobozba helyezünk át golyókat, akkor az üres dobozok száma értelemszerűen 1-gyel növekszik. Ezzel párhuzamosan az üres és a rendes dobozok számát tekintve, az összeg egyik tagja 1-gyel nőtt, míg a másik tagja legfeljebb 1-gyel csökkenhetett ($d_i$ nem lehetett rendes, egyedül $d_j$-t ,,ronthattuk el''), tehát az összeg nem csökkent. $\left(ii\right)$ Ha az adott lépésben a $d_i$ dobozból az üres $d_j$ dobozba helyeztük a golyókat (azaz egy ,,kör'' végére értünk), úgy az üres dobozok száma változatlan maradt, míg a $d_j$ doboz rendessé vált, tehát másik vizsgált mennyiségünk 1-gyel nőtt. A fentiek értelmében nyilvánvaló, hogy a játékot a lehetőségek kimerüléséig ismételve áldozatunk legfeljebb $2\left(k-1\right)$ lépés megtételét követően biztos lehet a szabadulásban; a lépésszám tetszőleges növelésére tett kísérleteink tehát nem jártak sikerrel.   2. megjegyzés. A becslés általános $k$-ra nem javítható, van ugyanis olyan $k$, amelyre ‐ megfelelő dobozokat választva ‐ a játékosnak a játék befejezéséhez pontosan $2k-2$ lépést kell megtennie. (Ennek részletes vizsgálatát az olvasóra bízzuk.)   Ismertetett játékunk eddigi változataiban a lépésszám lehetséges maximumának meghatározásához elégséges volt egy-egy megfelelően megválasztott mennyiség változását nyomon követni, és ennek segítségével különösebb nehézségek nélkül sikerült éles felső korlátot adni a lépésszám maximumára. További szemlélődéseink során az elsőként ismertetett ,,egyszerű dobozos játék'' egy lehetséges nehezített változatát vizsgáljuk. Az egy lépéses és iterált változatokat vizsgálva már igazoltuk, hogy a játék során megtett lépések számának lehetséges maximuma a dobozok számával azonos nagyságrendű. A következőkben bemutatásra kerülő játék az előzőekkel azonos színtéren zajlik, ám ellenfelünk ezúttal nem mindennapi képességekkel rendelkezik.   Játék a varázsló ellen   Az előttünk álló asztalon $k$ db ($k\ge 2$), 1-től $k$-ig sorszámozott, kezdetben üres doboz található, a már megszokott rendben. A játék megkezdése előtt a dobozokba ismét $k$ golyót helyezünk el. Ellenfelünk azonban egy varázsló, aki (többek között) az alábbi mágikus képességgel bír: pálcájának egyetlen suhintására az összes nem üres és nem rendes dobozban lévő golyó egyszerre kiemelkedik a dobozából, és az eredetileg $s$ sorszámú, $g$ golyót tartalmazó doboz összes golyója a $g$ sorszámú dobozba lebeg át (mintha az összes dobozba láthatatlan szellemkezek nyúltak volna, és végeznék párhuzamosan a játék előző változatában előírtakat). A golyók mágikus vándorlásának végeztével a varázsló megtekinti a dobozokat. Amennyiben suhintását követően a dobozok mindegyike üressé vagy rendessé vált, elégedetten összekulcsolja kezeit, és befejezi a játékot. Ellenkező esetben pálcájával ismételten suhint, elvégezve az előbb ismertetett varázslatot. Mindezt addig ismétli, amíg az asztalon lévő dobozok mindegyike üressé vagy rendessé nem válik.   3. feladat. Igazoljuk, hogy a varázsló tetszőleges elrendezés esetén véges sok suhintással eléri a kívánt végállapotot, és becsüljük meg a szükséges suhintások számát.   Korábbi eredményeinket felhasználva nyilvánvaló, hogy a kívánt állapot tetszőleges kezdőhelyzetből véges sok suhintás elvégzésével elérhető; ehhez mindössze annyit kell tennünk, hogy a játék folyamán ismét az üres dobozok számának változását követjük nyomon. Az üres dobozok száma jelen esetben is kezdetben legalább 0. Lépéseink során a vizsgált mennyiség értelemszerűen nem csökken (egyetlen doboz tartalmát sem osztjuk egynél több részre), ám ennél több is igaz: amennyiben az üres dobozok száma nem növekedett egy adott lépés során, úgy a lépés előtt rendes dobozok egyikébe sem helyezhettünk golyót (és egy dobozba legfeljebb egy másik dobozból érkezhetett golyó). Így a lépés után minden doboz üressé, vagy rendessé vált, tehát a játék véget ért. Mivel az üres dobozok számának lehetséges maximuma $k-1$, a vizsgált mennyiségünk legfeljebb $k-1$ alkalommal növekedhetett, tehát a játék legfeljebb $k$ lépésben véget ért. Az alábbiakban megmutatjuk, hogy korábbi becslésünket erősebb, és ‐ reményeink szerint ‐ általánosan tovább nem élesíthető felső korlátra cserélhetjük.   1. lemma. Az első suhintástól kezdve tetszőleges (aktuálisan) nem üres dobozban található golyók száma a doboz sorszámának többszöröse; tetszőleges nem üres és nem rendes dobozban található golyók száma a doboz sorszámának valódi többszöröse.   Bizonyítás. Tetszőleges dobozt vizsgálva, a suhintás előtt benne található golyók a suhintás során távoztak, vagy számuk éppen a doboz sorszámával egyező. Ha a suhintás során más dobozból érkezett golyó, akkor minden egyes dobozból a sorszámmal megegyező számú érkezett; ennek értelmében a sorszám valóban osztja a suhintást követően a dobozban található golyók számát. Amennyiben a doboz nem rendes, úgy a sorszám és a suhintás után tartalmazott golyók száma nem egyezhet meg, tehát a sorszám valódi osztó.   2. lemma. Tetszőleges $m$ pozitív egész esetén a varázsló $m$-edik suhintása során (feltéve, hogy az bekövetkezett) bármely nem üres és nem rendes doboz esetén a dobozból kilépő golyók száma legalább $2^{m-1}$.   Bizonyítás. Az állítás $m=1$ esetén triviális. A bizonyítást teljes indukcióval végezzük: ha valamely $m$-re a lemma állítását beláttuk, tekintsünk egy tetszőleges, az $m$-edik lépést követően nem üres és nem rendes, $s$ sorszámú $d$ dobozt. Az $m$-edik lépés során a $d$ dobozba legalább egy másik dobozból érkezett golyó (ellenkező esetben üressé vagy rendessé vált volna), mindegyikből pontosan $s$; az első lemma értelmében ekkor az $m$-edik lépés után a $d$ doboz legalább $2s$ golyót tartalmaz. Indukciós feltevésünk értelmében $s\ge 2^{m-1}$, így az $\left(m+1\right)$-edik lépésben a $d$ dobozból valóban legalább $2^m$ golyó lép ki.   Elért eredményeink birtokában tegyük fel, hogy a golyók egy adott elrendezése esetén a varázsló $n$ lépés megtételével fejezte be a játékot. Ekkor az $n$-edik lépés előtt értelemszerűen található nem üres és nem rendes doboz; ebből a dobozból második lemmánk értelmében az $n$-edik lépés során legalább $2^{n-1}$ golyó távozott. Mivel dobozainkban összesen $k$ golyó található, vizsgált dobozunk is legfeljebb ennyit tartalmazhatott, azaz $2^{n-1}\le k$. Így $n\le \left[\text{log}{}_{2}k\right]+1$. Ezután belátjuk, hogy ismertetett becslésünk általánosságban tovább már nem javítható, azaz, megfelelő $k$ választása mellett található olyan elrendezése a golyóknak, mellyel a varázslót $\left[\text{log}{}_{2}k\right]+1$ lépés megtételére kényszeríthetjük.   4. feladat. Legyen k=$2^m$, ahol $m$ pozitív egész. Igazoljuk, hogy ekkor létezik olyan elhelyezése a $2^m$ golyónak, melynél $m+1$ lépés szükséges a végállapot eléréséhez.   Az alábbiakban bemutatunk egy lehetséges elrendezést: helyezzünk $i=\mathrm{0,1,}\text{...}\mathrm{,}m-1$ esetén $2^i$ golyót a $2^i$-edik dobozba; 1 golyót a $2^m$ sorszámú dobozba, az eddig nem említett dobozokat pedig hagyjuk üresen (nem is tehetünk mást, hiszen a rendelkezésünkre álló golyókat már mind felhasználtuk). Az ismertetett eljárást ebből az állapotból indítva a végállapot eléréséhez valóban $m+1$ lépés megtétele szükséges, ennek ellenőrzését az olvasóra bízzuk.   Lépésszám becslése tetszőleges dobozszám esetén   Az ismertetett eredmények fényében meggyőződhettünk ugyan arról, hogy megfelelő $k$ választása esetén a varázsló valóban $\left[\text{log}{}_{2}k\right]+1$ lépés elvégzésére kényszerül, általános esetben azonban egyelőre nem áll rendelkezésünkre élességet igazoló konstrukció, ezáltal tetszőleges $k$ esetén a lépésszám elérhető maximuma, sőt még nagyságrendje sem ismert előttünk. Az élesség vizsgálatát előkészítendő, elsőként igazoljuk, hogy tetszőleges $k$ esetén a maximális lépésszám nagyságrendje korábban ismertetett korlátunkéval egyező, sőt, ennél több is elmondható: a pontos érték a megadott korlátnál legfeljebb 1-gyel lehet kisebb.   5. feladat. Megfelelő konstrukció készítésével igazoljuk, hogy tetszőleges $k$ esetén készíthető olyan elrendezése a golyóknak, mellyel a játékos $\left[\text{log}{}_{2}k\right]$ lépés megtételére kényszeríthető.   A feladat megoldása során a korábbiakra hivatkozva feltehetjük, hogy $k$ nem 2-hatvány. Konstrukciónkban legyen ekkor $k=2^m+r$, ahol $0<r<2^m$. Helyezzünk $i=\mathrm{0,1,}\text{...}\mathrm{,}m-2$ esetén a $2^i$ sorszámú dobozokba sorszámukkal megegyező számú golyót, a $\left(2^{m-1}\right)$ sorszámú dobozba egyetlen golyót, míg a megmaradt golyókat (összesen $2^{m-1}+r$ db-ot) helyezzük a $2^{m-1}+r$ sorszámú dobozba, a többi dobozt hagyjuk üresen. Látható, hogy a $2^{m-1}+r$ sorszámú dobozt már kezdetben rendesnek készítettük, és e tulajdonságát a játék során csak úgy veszíthetné el, ha a dobozba más dobozokból legalább $2^{m-1}+r$ golyó érkezne; ennyi golyó azonban nem található a dobozon kívül, így az értelemszerűen rendes marad a játék végéig. Készített konstrukciónk tehát azonos módon viselkedik $2^{m-1}$ golyóra adott elrendezésünkkel; végállapotában a $2^{m-1}$ és $2^{m-1}+r$ sorszámú dobozok rendesek, minden más doboz pedig üres. Az állapot eléréséhez értelemszerűen $m$ lépés szükséges, ezzel állításunkat igazoltuk. Fenti eredményeinket összesítve tehát, az alábbiak mondhatóak el a varázsló tevékenységéről:   Eredmény: Tetszőleges $k$ esetén a varázsló a játékot legfeljebb $\left[\text{log}{}_{2}k\right]$, vagy $\left[\text{log}{}_{2}k\right]+1$ lépésben fejezi be.   A nagyságrend megfelelő becslése, majd a lehetőségek számának drasztikus csökkentése után természetes célkitűzés a lépésszám maximumának pontos meghatározása általános $k$ érték esetén. A teljes áttekintéshez azonban néhány további akadály és nem várt nehézség leküzdése szükségeltetik, melyre jelen cikk keretei között nem vállalkozhatunk. Továbbra is szeretném azonban bátorítani az olvasót a kitűzésre került probléma elemzésére. Az ,,általános lépésszám-jellemzés'' problémaköréről várhatóan az újság januári számában olvashat további eredményeket az érdeklődő.