Feladat: Gy.2713 Korcsoport: 16-17 Nehézségi fok: átlagos
Füzet: 1992/február, 71. oldal  PDF  |  MathML 
Témakör(ök): Indirekt bizonyítási mód, Kombinatorika, Konstruktív megoldási módszer, Kettes alapú számrendszer, Gyakorlat
Hivatkozás(ok):Feladatok: 1991/szeptember: Gy.2713

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.

Először azt bizonyítjuk be, hogy ez megtehető hét lépésben; például a következő módon.

 
1. lépés: a 63-nál több kavicsot tartalmazó halmokból elveszünk 64-et. Így ezekben legfeljebb 36, a többiben legfeljebb 63 marad, vagyis nincs 63-nál több kavicsból álló halom.
 
2. lépés: Ahonnan lehet, elveszünk 32 kavicsot. Az előzőhöz hasonló gondolatmenettel látható, hogy ekkor minden halomban legfeljebb 31 kavics lehet.
 
3. lépés: 16 kavicsot vegyünk el a megfelelő halmokból. Ekkor mindenhol legfeljebb 15 maradhat.
 
Innen már látható a módszer: a 4. lépésben 8-at véve el, mindenhol legfeljebb 7 marad; az 5. lépésben 4-et veszünk el, marad legfeljebb 3; ezután 2-t elvéve mindenhol maximum 1 maradhat; a 7. lépésben pedig ezt az egyet elvéve, készen vagyunk.
Most azt látjuk be, hogy hat lépésben ezt nem tehettük volna meg. Tegyük fel, hogy mégis: a hat lépés során rendre a1, a2, ..., a6 kavicsot véve el bizonyos halmokból, a végén mindegyik kiürült.
Rendeljünk hozzá minden halomhoz egy legfeljebb hatjegyű kettes számrendszerbeli kódszámot a következőképpen. A szám i-edik jegye (i=1,2,...,6) legyen 1, ha vettünk el kavicsot a halomból az i-edik lépésben (ekkor csak ai-t vehettünk el); és legyen 0, ha nem. Ezáltal minden halomhoz egyértelműen hozzárendeltünk egy ilyen számot. Ugyanakkor egy ilyen szám csak egy halomhoz tartozhat, hiszen érvényes a következő dekódolási eljárás. Az x6x5x4x3x2x12¯ szám azt jelenti, hogy az első lépésben x1⋅a1 kavicsot vettünk el (x1 0 vagy 1 lehet), a másodikban x2⋅a2-t, azaz a hat lépés során összesen  x1a1+x2a2+...+x6a6-ot. A végeredmény viszont 0 lett, azaz a halomban eredetileg x1a1+...+x6a6 kavics volt; a kódból így megmondhatjuk, melyik halomhoz tartozik.
Mivel 100 különböző méretű halomból indultunk ki, azért 100-féle kódszámot kellett volna kapnunk. Azonban legfeljebb hatjegyű szám csak 64 van a kettes számrendszerben (sőt, a csupa 0 például nem is állhat elő kódszámként); ez ellentmond előző észrevételünknek, tehát hat lépésben nem lehet elszedni az összes kavicsot.