Pataki-probléma
A következő feladatot Pataki Jánostól hallottuk a berzsenyis matektáborban. A játék a Mankala egy egyszemélyes változata.
Van néhány dobozunk, sorszámozva, bennük néhány golyó. Adott továbbá egy gyűjtő. Egy lépésben a k. sorszámú doboz kiüríthető, ha pontosan k golyó van benne. Ilyenkor minden kisebb sorszámú dobozba teszünk egy-egy golyót, és a megmaradó egy a gyűjtőbe kerül.
Kiüríthető doboz
Kiürítés
Lépés utáni állapot
A táborban megbeszéltük a játék matematikáját, azt most nem kell kitalálni. A következő állítások igazak:
- Mindig a legkisebb dobozt kell kiüríteni, ami tele van (vagyis annyi golyó van benne, amennyi az indexe).
- Tehát, ha a játék megoldható, akkor csak egyféle megoldása van. (Persze ez így akkor nem is játék.)
- Bármely n számú golyó szétpakolható megfelelő számú dobozba úgy, hogy ez a szétpakolás megoldható.
- Az előző elrendezés egyértelmű
- Tehát minden n golyószámhoz van egyetlen megfelelő k dobozszám, ami azt jelenti, hogy az n golyó leszedhető elrendezéséhez kezdetben k doboz kell. (A k sorszámú doboz nem üres, a k-nál nagyobb sorszámúak üresek.)
- Most jön a varázslat: egy csodaszép ötlet segítségével bizonyítható, hogy a kezdeti elrendezésre igaz a következő:
$x_i \equiv 0 ~mod~ (i+1)$,
ahol $x_i$ a kezdeti golyószám az i. dobozban.
Feladatok
- Adott golyószámra adjuk meg a megoldható elrendezést!
- Adott elrendezést játsszunk le!
- Készítsük el SVG grafikával adott golyószámra a kezdeti elrendezést! (Kis n-re körökkel, nagy n-re vonaldiagrammal.)
Minta
Uray János programja által generált képek:
