Van 9 érme és a 9 érme közül az egyik hamis. Hány mérés kell hozzá, hogy megtudjuk melyik az igazi? Pl: igazság mérleg két oldalára rakunk 2-2 és ha egyenlő akkor az a hamis amelyik kimaradt.

Köszi mindenkinek de meg találtam. DE ha valakit érdekel a megfejtés itt van: A) Osszuk 3db 3 elemû csoportba az érméket. Két csoportot hasonlítsunk össze. Ha az egyik csoport nehezebb a másiknál, akkor abban van a hamis érme, ha egyenlõek, akkor a harmadikban. Ezek után 3 elem közül kell kiválasztani a hamisat, amit az elõzõ esethez hasonló módon teszünk: Kettõt összemérünk, ha az egyik nehezebb, akkor az a hamis, ha egyenlõek, akkor a harmadik. Így tehát 2 mérés elegendõ a hamis érme meghatározásához.

n érme esetén tegyük fel, hogy n=3^k alakú. Ezesetben elsõ mérésnél 3db 3^(k-1) elemû csoportot alakítunk ki, (és teljesen hasonlóan járunk el, mint 9 érme esetén) majd 3db 3^(k-2) elemû csoportokat és így tovább... Tehát ezesetben log3(n) lépésre van szükség.

Ha n nem 3^k alakú, hanem 3^(k-1) < n < 3^k, akkor 2db 3^(k-1) elemû csoportot alakítunk ki, a maradék kerül a 3. csoportba. Rossz esetben (ha nem a kis csoportban van a hamis) ugyanannyi mérés kell, mint n=3^k esetben. Tehát általánosan FelsõEgészrész(log3(n)) lépésre van szükség!