Kezdőlap


Feladat:	Gy.2225	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	1985/május, 214 - 216. oldal		PDF \| MathML
Témakör(ök):	Egész számok összege, Játékelmélet, játékok, Szöveges feladatok, Klasszikus valószínűség, Várható érték, Gyakorlat
Hivatkozás(ok):	Feladatok: 1984/november: Gy.2225

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 F. 2494. megoldása is.) Általában, $n \geq 2$ golyó esetén válaszoljuk meg a feladat kérdését. A nyereség helyett vizsgáljuk a veszteséget! Ez a mérések, valamint a radioaktívvá vált golyók számának az összege. Feladatunk megkeresni: mi a lehető legkisebb veszteség.
Jelölje $H_{k}$ az első $k$ darab pozitív egész összegét, azaz legyen $H_{k} = \frac{k (k + 1)}{2}$ , az úgynevezett $k$ -adik ,,háromszögszám''. Állítjuk, hogy ha $n \leq H_{k} + 1$ , akkor van olyan mérési eljárás, amelynek során legfeljebb $k + 1$ forintot veszítünk, míg ha $n > H_{k} + 1$ , akkor bármilyen módszerrel próbálkozzunk is, ennek során előfordulhat, hogy veszteségünk legalább $k + 2$ forint.
Legyen tehát először $n \leq H_{k} + 1 = k + (k - 1) + (k - 2) + ... + 2 + 2$ . Ekkor léteznek olyan $a_{1}$ , $a_{2}$ , $...$ , $a_{k - 1}$ nem negatív egészek, hogy

\begin{matrix} n = a_{1} + a_{2} + ... + a_{k - 1} + 2, \end{matrix}

(1)

továbbá

\begin{matrix} a_{1} \leq k, a_{2} \leq k - 1, ..., a_{k - 1} \leq 2 . \end{matrix}

Valóban, ha

n = H_{k} + 1

, akkor az

\begin{matrix} n = k + (k - 1) + ... + 2 + 2 \end{matrix}

választás megfelelő, ha pedig

n < H_{k} + 1

, akkor egyes

a_{i}

-ket alkalmasan csökkentve elérhető az előállítás.
Osszuk ezután a golyókat (1) szerint

k

csoportba úgy, hogy az egyes csoportokban rendre

a_{1}, a_{2}, ..., a_{k - 1}

, illetve az utolsóban

2

darab golyó legyen. Mérjük meg ebben a sorrendben először az

a_{1}

darab, majd az

a_{2}

darab golyót, és így tovább egészen addig, amíg egy ,,sugárzó'' csoportra nem találunk, illetve ha a

(k - 1)

-edik csoport is ,,egészséges'' volt, akkor itt hagyjuk abba ‐ tehát a maradék

2

golyóval ne törődjünk.
Ha az

i

-edik mérésre találjuk meg a sugárzó golyót

(i ≦ k - 1)

, akkor veszteségünk

i + a_{i}

forint, ami

a_{i} \leq k - (i - 1)

szerint legfeljebb

k + 1

. Ha pedig a

k - 1

darab mérés során nem találtunk sugárzó golyót, akkor veszteségünk az elvégzett mérések költsége és a megmaradt

2

golyó, de ez most sem több

k + 1

forintnál. Ezzel állításunk első felét igazoltuk.
Legyen most

n > H_{k} + 1

és tegyük fel, hogy létezik olyan mérési eljárás, amelynek során a veszteség legfeljebb

k + 1

forint, bármilyen is legyen a golyók sorrendje mérés közben.
Ha az

i

-edik mérés során

a_{i}

darab golyót mérünk egyszerre, akkor nyilván

a_{i} + 2 \leq (k + 1)

-nek fenn kell állnia, hiszen ha véletlenül éppen ezek között van a radioaktív golyó, akkor ezzel a méréssel együtt

a_{i} + i

forint a veszteségünk. (Azt a lehetőséget nyilván kizárhatjuk, amikor valamennyi mért golyóról tudjuk, hogy egészséges, hiszen ilyen mérést nem végzünk.)
Ez azt jelenti, hogy

l \leq k

-ra

l

méréssel legfeljebb

k + (k - 1) + ... + (k - l + 1)

golyót vizsgálhatunk át. Így a még nem mért golyók száma legalább

\begin{matrix} n - (k + (k - 1) + ... + (k - l + 1)) \geq H_{k} + 2 - (k + (k - 1) + ... + (k - l + 1)) = \\ = 2 + (k - l) + (k - l - 1) + ... + 1 \geq 2 + (k - 1) . \end{matrix}

i

-edik mérés után még legalább

(k - l) + 2

golyót nem vizsgáltunk meg. Ha eddig valamennyi golyó egészséges volt és abbahagyjuk a mérést, veszteségünk legalább

l + (k - l) + 2 = k + 2

forint. Ha viszont

(k + 1)

-edszer is mérünk, és éppen akkor találunk sugárzó golyót (golyókat), a veszteség ismét legalább

k + 2

forint.
Beláttuk tehát, hogy

n > H_{k} + 1

esetén bárhogyan is próbálkozunk, előfordulhat, hogy veszteségünk (balszerencsés esetben) legalább

(k + 2)

forint.
Ha tehát

H_{k}

jelöli az

(n - 1)

-nél nem nagyobb háromszögszámok legkisebbikét, akkor mindenképpen biztosíthatjuk, hogy

k + 1

forint legyen a veszteségünk, ennél kevesebbet azonban már nem. Így az üzleten legfeljebb

n - k - 1

forintot nyerhetünk biztosan. Mivel

H_{3} = 6, H_{4} = 10

, azért

n = 10

-re

k = 4

, azaz legfeljebb

10 - (4 + 1) = 5

forintot nyerhetünk, a megoldás első része alapján például a következő csoportosítással:

a_{1} = 3, a_{2} = 3, a_{3} = 2, a_{4} = 2

.
Ha

n = 100

, akkor

H_{13} = 91, H_{14} = 105

alapján

k = 14

, így legfeljebb

100 - (14 + 1) = 85

forint nyereséggel számolhatunk biztosan. Egy lehetséges méréssorozat:

\begin{matrix} a_{1} = 14, a_{2} = 13, ..., a_{10} = 5, a_{11} = 3, a_{12} = 0, a_{13} = 0, a_{14} = 2. \end{matrix}

Megjegyzések. 1. Némi számolás után adódik, hogy

n

darab golyó esetén az elérhető nyereség

\begin{matrix} [\frac{2 n - 1 - \sqrt[]{8 n - 7}}{2}] forint. \end{matrix}

2. A megoldásban azt kerestük, mennyi az a nyereség, amit a ,,legrosszabb'' esetben is megszerezhetünk. Azt is vizsgálhatnánk, hogy mi a maximális nyeremény várható értéke. A kérdés nem könnyű, itt csak egy példán szemléltetjük, miről van szó.
A mérést úgy végezzük, hogy a golyókat

a_{1}

a_{2}

...

a_{k}

méretű kupacokra vágjuk szét, majd sorban az

a_{1}

a_{2}

stb. méretű kupacot küldjük el megmérni (az utolsó kivételével). Ha a radioaktív golyó az

i

-edik kupacban van ‐ ennek valószínűsége

a_{i} / n

‐, veszteségünk

a_{i} + i

. Így a veszteség várható értéke

\begin{matrix} \frac{a_{1}}{n} (1 + a_{1}) + \frac{a_{2}}{n} (2 + a_{2}) + ... + \frac{a_{k - 1}}{n} (k - 1 + a_{k - 1}) + \frac{a_{k}}{n} (k - 1 + a_{k}) . \end{matrix}

100

golyónak a megoldásban ismertetett csoportosítására ez az érték

\begin{matrix} \frac{14}{100} (14 + 1) + \frac{13}{100} (13 + 2) + ... + \frac{5}{100} (5 + 10) + \\ + \frac{3}{100} (3 + 11) + \frac{2}{100} (2 + 11) = 14, 93, \end{matrix}

vagyis a veszteség várható értéke valamivel kevesebb, mint

15

, ami természetes, hisz az esetek két századrészében már

11

mérés után kiderül, hogy a megmaradt golyók között van a sugárzó.
Az egyik optimális csoportosítás az alábbi:

\begin{matrix} a_{1} = 10, a_{2} = a_{3} = 9, a_{4} = a_{5} = 8, a_{6} = a_{7} = 7, a_{8} = a_{9} = 6, a_{10} = a_{11} = 5, \\ a_{12} = a_{13} = 4, a_{14} = a_{15} = 3, a_{16} = a_{17} = a_{18} = 2. \end{matrix}

Ebben az esetben ugyan előfordulhat, hogy a veszteségünk több lesz

15

forintnál, azonban ennek a valószínűsége kicsi. Ha viszont az első

7

mérés valamelyikében akadunk a sugárzó golyóra, akkor a veszteség csak

13

vagy

14

forint, tehát érdemes kockáztatni. Maga a várható érték ebben az esetben

13, 84

forint, azaz ilyenkor átlagosan körülbelül

1

forinttal nyerhetünk többet, mint az előbb.