NézetNyomtat

Pataki-probléma (Megoldás)
Címkék > Feladat

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

  1. Adott golyószámra adjuk meg a megoldható elrendezést!
  2. Adott elrendezést játsszunk le!
  3. 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: