Az A. 542. feladat (2011. október)

A. 542. Van 1000 pénzérménk, de tudjuk, hogy közülük 100 hamis. Ismerjük a valódi érmék súlyát, és tudjuk, hogy a hamis érmék könnyebbek, mint a valódiak, de a hamis érmék súlyai különbözők is lehetnek. Egy egykarú mérleggel szeretnénk találni egy hamis érmét. Minden lépésben megmérhetjük néhány érme súlyának összegét, ezzel megállapíthatjuk, hogy a mérlegre tett érmék között van-e hamis. Hány mérésre van szükségünk, hogy biztosan találjunk egy hamis érmét?

Javasolta: Pálvölgyi Dömötör (Budapest)

(5 pont)

A beküldési határidő 2011. november 10-én LEJÁRT.

Megoldásvázlat. A szokásos felezgetéses módszerrel 10 méréssel biztosan találhatunk hamis érmét. Megmutatjuk, hogy 9 mérés viszont nem elég.

Tegyük fel, hogy van egy legfeljebb 9 mérésből álló eljárás, ami minden esetben kiválaszt egy érmét. Most csak a determinisztikus eljárásokra szorítkozunk; a véletlen választásokat tartalmazó eljárások esetén minden véletlen döntésnél előre előírhatjuk az adott választást.

Az eljárás minden lehetséges "lefutását" egy-egy, legfeljebb 9 hosszú igen-nem sorozattal kódolhatjuk. Azokban az esetekben, amikor az eljárás 9-nél kevesebb méréssel véget ér, az igen-nem sorozatot egészítsük ki igenekkel. Ilyen módon az eljárás minden lehetséges lefutásához hozzárendeltünk egy pontosan 9 hosszúságú igen-nem sorozatot.

Mivel csak 2⁹=512 igen-nem sorozat van, az eljárásnak legfeljebb 512-féle eredménye lehet; az eljárás az érmék közük csak 512-t tud hamisként megjelölni. Ha viszont a hamis érmék a többi 488 érme között vannak, akkor az eljárás nem adhat helyes eredményt.

Statisztika:

15 dolgozat érkezett.
5 pontot kapott:	Ágoston Tamás, Janzer Olivér, Mester Márton, Omer Cerrahoglu, Strenner Péter.
4 pontot kapott:	Bodnár Levente, Gyarmati Máté.
2 pontot kapott:	3 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	3 versenyző.

A KöMaL 2011. októberi matematika feladatai