Feladat: F.2412 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Bartha 562 M. ,  Blum G. ,  Bóna M. ,  Böröczky L. ,  Csillag P. ,  Csizmadia Gy. ,  Danyi P. ,  Dobos B. ,  Erdős 228 L. ,  Gáspár Zsuzsanna ,  Gulyás Éva ,  Gyuris V. ,  Hetyei G. ,  Horváth A. ,  Horváth A. ,  Horváth B. ,  Hraskó A. ,  Ispány Márton ,  Kapovits Á. ,  Katona Gy. ,  Kós G. ,  Ladányi L. ,  Makay G. ,  Márkus A. ,  Megyesi G. ,  Mócsy M. ,  Pásztor L. ,  Peták T. ,  Petrovics Gyöngyi ,  Réz A. ,  Ribényi Ákos ,  Simon P. ,  Szabó 112 T. ,  Szabó 983 T. ,  Szabó Cs. ,  Szakállas Gy. ,  Szapudi I. ,  Szeier T. ,  Tóth G. ,  Törőcsik J. ,  Zsigri G. 
Füzet: 1983/november, 124. oldal  PDF file
Témakör(ök): Játékelmélet, játékok, Teljes indukció módszere, Feladat
Hivatkozás(ok):Feladatok: 1983/március: F.2412

Van d darab dobozunk és egy urnánk. A dobozok 1-től d-ig meg vannak számozva, és közülük néhányban ‐ esetleg mindegyikükben ‐ golyók vannak. Az a célunk, hogy a dobozok tartalmát az urnába gyűjtsük össze. Az i-edik doboz akkor üríthető ki, ha pontosan i darab golyó van benne, a kiürítés pedig úgy történik, hogy a golyók közül egyet az urnába teszünk, a maradék (i-1)-et egyesével az első, második, ..., (i-1)-edik dobozba.
Milyen n-re helyezhető el megfelelő számú dobozba n darab golyó úgy, hogy valamennyit összegyűjthessük az urnába?

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 feladat minden természetes számra megoldható, erre most teljes indukciós bizonyítást adunk.
n=1-re a golyót az első dobozba tesszük. n-ről (n+1)-re a következő módszerrel léphetünk. Tegyünk a legkisebb sorszámú üres dobozba a doboz sorszámával megegyező számú golyót és vegyünk ki a nála kisebb sorszámú (nem üres!) dobozokból egyet‐egyet. Ezzel a dobozokba együttvéve eggyel több ‐ azaz (n+1) ‐ golyót helyeztünk el. Ha most a szóban forgó dobozt kiürítjük, helyreáll az előző állapot, amiről az indukciós feltevés miatt tudjuk, hogy megfelelő.
Ezzel megmutattuk, hogy (n+1)-re, és így minden természetes számra van megfelelő elhelyezés.

 

 Ribényi Ákos (Bp., I. István Gimn., I. o. t.)
 dolgozata alapján