Feladat: Gy.2111 Korcsoport: 16-17 Nehézségi fok: átlagos
Füzet: 1984/január, 17 - 19. oldal  PDF  |  MathML 
Témakör(ök): Játékelmélet, játékok, Konstruktív megoldási módszer, Gyakorlat
Hivatkozás(ok):Feladatok: 1983/március: Gy.2111

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.

Megadunk egy jó elrendezést:

 
a dobozok sorszáma      1  2 3 4 5 6 7 8a golyók száma     1 1 3 4 2 4 6 8

 
Ha minden lépésben a legkisebb sorszámú kiüríthető dobozból vesszük ki a golyókat, akkor a táblázat mutatja, hogy az egyes lépések során hányas számú dobozt kell kiürítenünk. Látható, hogy a 29-edik lépés után valamennyi golyó az urnába kerül.
 
Megjegyzés. A fenti megoldást sokan megtalálták, többen igazolták azt is, hogy ez az egyetlen. Számos dolgozatból hiányzott azonban, hogy a dobozok kiürítése valóban megvalósítható.
A táblázat elkészítése és nyomon követése már itt is elég fáradságos, több golyó esetén pedig még inkább az volna. Az alábbi gondolatmenet úgy ad módszert a megfelelő elrendezés elkészítésére, hogy egyúttal annak helyességét is bizonyítja.
Ha Si jelöli az i-nél nem kisebb sorszámú dobozokban levő golyók számának összegét egy tetszőleges doboz kiürítése előtt, si pedig a doboz kiürítése után, akkor Si-si értéke 0 vagy i aszerint, hogy az éppen kiürített doboz sorszáma kisebb-e, mint i vagy sem. Mivel az eljárás végén egyetlen dobozban sem maradhat golyó, kapjuk, hogy Si kezdeti értékeire fenn kell álljon, hogy minden i-re i|Si. Másrészt nyilván teljesülnie kell, hogy egyetlen dobozban sem lehet több golyó, mint a doboz sorszáma, vagyis a fenti jelöléssel Si+1-Si≦i minden i-re.
Vegyük észre, hogy ez a két feltétel már meghatározza az i-edik doboz kezdeti tartalmát. Ha ugyanis ezt a mennyiséget ai-vel jelöljük, akkor
Si=ai+Si+1.

Mivel Si+1 osztható (i+1)-gyel, másrészt 0≦ai<(i+1), azért ai éppen az a maradék, amit Si-nek az (i+1)-gyel való osztásakor kapunk. i=1-től indulva ai értékei rendre meghatározhatók:
 
 iSi i+1 ai 129 2 1  228 3 1  327 4 3  424 5 4  520 6 2  618 7 4  714 8 6  88 9 8  90 10 0 ⋮⋮ ⋮ ⋮

 

Lépésszám  \  Doboz száma1.   2.3.4.5.6.7.8.1  •13424682  12•424683  •20424684  1•0424685  •00424686  111•24687  •11024688  1221357•9  •22135710  1•2135711  •02135712  113246•13  •1324614  12•24615  •2024616  1•024617  •0024618  11135•19  •113520  1224•21  •22422  1•2423  •02424  113•25  •1326  12•27  •228  1•29  •


Az ily módon kapott elrendezésre teljesül a talált két feltétel:
 
(a) i|Si minden i-re;
(b) 0≦ai≦i minden i-re.
 
Megmutatjuk, hogy ha ez a két feltétel teljesül, akkor vagy minden doboz üres, vagy pedig van olyan doboz, amelyet kiürítve a két feltétel továbbra is igaz marad.
Ha nem minden doboz üres, akkor az utolsó nem üres doboz sorszámát k-val jelölve (a) szerint k|Sk . Ugyanakkor az utolsó nem üres dobozról lévén szó Sk=ak, tehát 0<ak≦k miatt ak=ki, vagyis az utolsó nem üres doboz biztosan kiüríthető.
Ha most a legkisebb sorszámú kiüríthető dobozból vesszük ki a golyókat, akkor (b) továbbra is igaz marad, hiszen csak olyan dobozokban nő ‐ mégpedig pontosan eggyel ‐ a golyók száma, amelyek eddig nem voltak kiüríthetők.
Mivel pedig Si-si osztható i-vel, ezért a kiürítés után az (a) feltétel is igaz marad.
Az eljárás tehát csak akkor nem folytatható, ha valamennyi doboz üres, vagyis a leírt módszerrel általában is megkapjuk az S1 darab golyó (egyetlen) kiüríthető elrendezését.