Hamis az érme?
Tovább a rejtvényhez 9 látszólag egyforma érme közül az egyik hamis: nehezebb a többinél. Hány méréssel lehet a hamis érmét egy kétkarú mérleg segítségével megtalálni? És n érme esetén?
Gondolkodóba estél?
Ha igen, akkor már jó úton jársz a megfejtéshez!
Tovább a rejtvényhez
1
9 látszólag egyforma érme közül az egyik hamis: nehezebb a többinél. Hány méréssel lehet a hamis érmét egy kétkarú mérleg segítségével megtalálni? És n érme esetén?
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!
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!
Kártya fordítása
Következő kérdés
Hamis az érme?
Eredmény számítása folyamatban . . .
A te eredményed
Hogy tetszett ez a rejtvény?
Ezeket is látnod kell!
Kommentek
Mi a véleményed? Oszd meg velünk!