Kezdőlap


Cím:	Hamis zsákok nyomában
Szerző(k):	Bege Antal
Füzet:	1988/március, 97 - 98. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

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.

Az alábbiakban egy klasszikusnak számító hamis-pénz probléma általánosításával foglalkozunk.
Először is lássuk az eredeti feladatot, amely megtalálható például Martin Gardner könyvében, aki talán a legnagyobb "élő klasszikusa'' a logikai fejtörőknek és játékoknak. Magyar nyelven Bizám György‐Herczeg János: Sokszínű logika című könyvében (Műszaki Könyvkiadó, 1975, 1986) olvashatunk a feladatról.
Van $10$ zsáknyi pénzünk. Az érmék látszatra egyformák, de az egyik zsák tartalma "hamis''; az itt lévő érmék $1$ grammal könnyebbek a többinél. Ismerve a valódi pénzérmék súlyát, az a feladatunk, hogy egy beosztásos mérleg segítségével egyetlen méréssel válasszuk ki a "hamis'' zsákot. Most és a továbbiakban föltesszük, hogy az egyes zsákokból korlátlan számú érmét vehetünk ki.
A megoldást valószínűleg sokan ismerik :
Számozzuk meg a zsákokat $1$ -től $10$ -ig és mindegyikből vegyünk ki annyi pénzérmét, amennyi a zsák sorszáma. Mivel ismerjük a "jó'' pénzérmék súlyát, előre ki tudjuk számítani, mennyit nyomna az így kivett összesen $1 + 2 + ... + 10 = 55$ érme, ha nem volna köztük hamis. Az érmék együttes súlyát lemérve nyilván annyi grammal kapunk kevesebbet az előbb kiszámított értéknél, ahányas sorszámú zsákban találhatók a "hamis'' pénzérmék.

A probléma

2

"hamis'' zsákos változata a következő :
Van

40

zsák látszólag egyforma pénzérme, de most

2

zsákban vannak hamis érmék, amelyek

1

grammal könnyebbek, mint a valódiak. Ha ismerjük a "jó'' érmék súlyát, akkor

2

méréssel keressük meg a

2

hamis zsákot.
A megoldás most a következő :
Megszámozzuk a zsákokat

1

-től

40

-ig, és most is a zsák sorszámával megegyező számú érmét veszünk ki az egyes zsákokból. Az előbbiek szerint ha az

1 + ... + 40 = 820

valódi érme súlyának összegéből kivonjuk a mérés eredményét, akkor a két hamis zsák sorszámának az összegét kapjuk. Legyen

k

az így kapott szám felének az egész része. Mivel a két sorszám különböző, az első hamis zsák sorszáma nem nagyobb, mint

k,

a másodiké viszont igen. Az első

k

darab zsák között tehát pontosan egy hamis van, ez pedig egy újabb méréssel kiválasztható. Ezután pedig a két hamis zsák sorszámának összegét ismerve megtalálhatjuk a másodikat is.
Ez a megoldás nem a legjobb. Az eddigi feltételek mellett tegyük föl, hogy

n

darab zsák között néhány hamis ‐ nem tudjuk, hogy mennyi ‐ és ezekben

1

grammal könnyebbek az érmék. Ekkor egyetlen méréssel is megtalálhatjuk az összes hamis zsákot.
Vegyünk ki ehhez az

1

-től

n

-ig megszámozott zsákok közül az

i

-edikből

2^{i - 1}

darab érmét

(i = 1, 2, ..., n) .

a_{i}

aszerint

1

vagy

0,

hogy az

i

-edik zsák hamis-e vagy sem, akkor a kivett érmék együttes súlya

\begin{matrix} \sum_{i = 1}^{n} (m - a_{i}) \cdot 2^{i - 1}, \end{matrix}

ahol

m

a valódi érmék súlya. Mivel

m

értékét ismerjük, így rendelkezésre áll a

\begin{matrix} \sum_{i = 1}^{n} a_{i} \cdot 2^{i - 1} \end{matrix}

összeg, ennek kettes számrendszerbeli alakjában a számjegyeik pedig éppen az

a_{i}

számok, amelyek mutatják az egyes zsákok jellegét.

A feladatnak ezt a változatát némileg módosíthatjuk.
Adott

n

zsák, közöttük néhány hamis, amelyek számát most sem ismerjük. Minden egyes hamis zsákban egyforma nehezek az érmék, de ez a súly zsákonként különbözhet. Tudjuk, hogy valamennyi érme súlya egész szám, a valódi érmék súlya

g

gramm, a hamis érmék pedig könnyebbek

g

-nél. Talán meglepő, hogy ebben az esetben is egyetlen méréssel megtalálhatók a hamis zsákok, és a bennük levő érmék súlyát is megtudhatjuk.
Vegyünk ehhez az

i

-edik zsákból

{(g + 1)}^{i - 1}

darab érmét

(1 ≦ i ≦ n) .

g_{i}

jelöli az érmék súlyát az

i

-edik zsákban, akkor a kivett érmék együttes súlya,

S = \sum_{i = 1}^{n} g_{i} \cdot {(g + 1)}^{i - 1} .

Föltevésünk szerint

1 ≦ g_{i} ≦ g,

így a

g_{i}

számok éppen a

(g + 1)

alapú számrendszerben felírt

S

szám számjegyei. A feladat előbbi változatával szemben most nagyon lényeges volt, hogy az érmék súlya egész szám. (A korábbiakban az

m

értékéről ezt nem kellett föltennünk.)
Vegyük észre, hogy a "valódi'' súly értékére csak annyiban volt szükségünk, hogy találhattunk egy olyan egész számot ‐ a

(g + 1)

-et ‐ amelyik valamennyi előforduló érme súlyánál nagyobb. Amennyiben ezt az értéket sem ismerjük, akkor két mérés szükséges a feladat megoldásához. Először minden zsákból egy-egy érmét kivéve megkaphatjuk a

G = g_{1} + g_{2} + ... + g_{n}

összeget, amely minden

g_{i}

-nél nagyobb, ezután pedig a

(g + 1)

helyett a

G

hatványaival dolgozva a fenti eljárással megtudhatjuk az egyes

g_{i}

értékeket.

Irodalom:
Martin Gardner:
First and Second Scientific American Books of Mathematical Puzzles and Diversions
Bizám György‐Herczeg János:
Sokszínű logika, 52., 53. feladatok
G. Sesztopol:
Hogyan keressük ki a hamis érmét?
KÖMAL, 1980/1 szám, 1‐5. old.