Az A. 387. feladat (2005. december)

A. 387. Van n látszólag egyforma golyónk, ami közül tudjuk, hogy az egyik radioaktív; ezt a golyót szeretnénk megtalálni. Egy radioaktivitást jelző műszer segítségével a golyók egy tetszőleges részhalmazáról el tudjuk dönteni, hogy a radioaktív golyó köztük van-e.

Olyan mérési stratégiát szeretnénk választani, amelyre a szükséges mérések számának várható értéke a lehető legkisebb. Határozzuk meg ezt a legkisebb lehetséges várható értéket.

(5 pont)

A beküldési határidő 2006. január 16-án LEJÁRT.

1. megoldás. Jelöljük a_n-nel a lehetséges legkisebb várható mérésszámot. Megmutatjuk, hogy 2^k $\le$ n $\le$ 2^k+1 esetén $a_n=k+\frac{2(n-2^k)}{n}$ . (Ha n éppen 2-hatvány, akkor ez a képlet kétféleképpen is ugyanazt az eredményt adja.)

Érdemes bevezetni a b_n=na_n sorozatot. Az állítás erre átírva:

b_n=kn+2(n-2^k).

Indukció. Triviálisan a₁=0 és a₂=1. Tegyük fel, hogy az állítás (n-1)-ig igaz, és vizsgáljuk az n golyó esetét. Az első mérésben mérjünk x golyót, ahol 1 $\le$ x<n. Ezek között $\frac{x}{n}$ valószínűséggel van a radioaktív, ilyenkor a_x további mérés szükséges. Ellenkező esetben a további mérések száma a_n-x. Összességében

$a_n=1+\min_{1\le x\le n-1} \left(\frac{x}{n}a_x+\frac{n-x}{n}a_{n-x}\right),$

vagyis

$b_n=n+\min_{1\le x\le n-1n}(b_x+b_{n-x}).$

(1)

Nem nehéz végigondolni, hogy m<n-1 esetén b_m+1-b_m=[log₂m]+2, ami monoton nő. Ezért a b₁,...,b_n-1 sorozat konvex, és (1)-ben a minimumot biztosan megkapjuk az x=[n/2] választás esetén. Ekkor x és n-x is a [2^k-1,2^k] intervallumba esik és

b_n=n+b_x+b_n-x=n+((k-1)x+2(x-2^k-1))+((k-1)(n-x)+2(n-x-2^k-1))=kn+2(n-2^k).

2. megoldás. A stratégiát egy bináris fán is ábrázolhatjuk. Az eljárás tetszőleges állapotában bizonyos golyók gyanúsak, ezek bármelyike lehet a radioaktív golyó; a többi golyó tiszta, ezekről már valamelyik korábbi mérés alapján tudjuk, hogy nem radioaktívak. A fa gyökere a kezdeti állapot, amikor is mindegyik golyó gyanús.

A fának kétféle cúcsa lesz:

-- elágazás: olyan állapot, amikor 1-nél több gyanús golyó van. Az ilyen csúcsokhoz odaírjuk, hogy mik a gyanús golyók golyóhalmazt mérjük meg következőnek. Az elágazásokból mindig két él indul ki, ezek végén a gyanús golyókat két diszjunkt részre osztjuk a méréstől függően.

-- levél: olyan állapot, amikor egyetlen gyanús golyó van. Ilyenkor az eljárás véget ér.

Az 1. ábrán azt a stratégiát ábrázoltuk, amikor n=5 és a golyókat egyesével mérjük.

1. ábra

Megfordítva, ha rajzolunk egy n levelű bináris fát, akkor azt stratégiává tudjuk konvertálni úgy, hogy a levelekhez odaírjuk az 1,2,...,n számokat, és minden csúcsba a belőle kiinduló két él végéhez írt halmazok unióját (2. ábra). A feladat tehát annak a fának a megtalálása, amelyben a levelek mélységének átlaga a lehető legkisebb.

2. ábra

Mindegyik golyóhoz tudjuk, hogy hány mérés szükséges a megtalálásához ; ez az érték éppen a megfelelő levél mélysége. A várható lépésszám pedig a levelek mélységeinek átlaga. Tekintsük most az egyik olyan fát, amelyben a levelek mélységének összege minimális. A legkisebb mélység legyen a, a legnagyobb b. megmutatjuk, hogy a és b legfeljebb 1-gyel különbözhet. Tegyük fel indirekte, hogy b>a+1.

A legmélyebb szinten a levelek párosával fordulnak elő. Hagyjuk el az egyik ilyen párt, és helyette az egyik a mélységű levél alá illesszünk be két új levelet (3. ábra).

3. ábra

A változtatás során megszűnik egy a és két b mélységű levél, helyettük keletkezik két a+1 és egy b-1 mélységű levél. A mélységek összegének változása (2(a+1)+(b-1))-(a+2b)=1-(b-a)<0, vagyis a mélységek összege csökken. Ez pedig ellentmond annak, hogy a mélységek összege minimális volt.

A legjobb stratégiák fáiban tehát legfeljebb csak kétféle, szomszédos mélység fordulhat elő; ez a két mélység legyen k és k+1. A fát úgy is felépíthetjük, hogy először veszünk egy k mélységű teljes fát, majd ennek néhány levelére egy-egy ,,cseresznyét'' -- két új, k+1 mélységű levelet illesztünk. Ha a hozzáillesztett cseresznyék száma x, akkor a fának 2^k+x levele van. Mivel x értéke legfeljebb 2^k, ez pontosan akkor lehetséges, ha 2^k $\le$ n $\le$ 2^k+1 és x=n-2^k.

A levelek mélységének átlaga

$\frac{(2^k-x)\cdot k+2x\cdot(k+1)}n =\frac{nk+2x}n=k+\frac{2(n-2^k)}n.$

Statisztika:

14 dolgozat érkezett.

5 pontot kapott: Erdélyi Márton, Estélyi István, Gyenizse Gergő, Hujter Bálint, Jankó Zsuzsanna, Nagy 224 Csaba, Paulin Roland, Sümegi Károly, Tomon István.

4 pontot kapott: Ureczky Bálint.

3 pontot kapott: 3 versenyző.

0 pontot kapott: 1 versenyző.

A KöMaL 2005. decemberi matematika feladatai

14 dolgozat érkezett.
5 pontot kapott:	Erdélyi Márton, Estélyi István, Gyenizse Gergő, Hujter Bálint, Jankó Zsuzsanna, Nagy 224 Csaba, Paulin Roland, Sümegi Károly, Tomon István.
4 pontot kapott:	Ureczky Bálint.
3 pontot kapott:	3 versenyző.
0 pontot kapott:	1 versenyző.

Már regisztráltál?
Új vendég vagy?