Výzvy k vážení mincí nebo kuliček byly vždy oblíbené mezi milovníky hádanek a matematických géniů. Jedním z nejznámějších úkolů tohoto typu je výzva k nalezení falešné mince mezi 27 mincemi. Jak těžké je tento problém vyřešit a kolik vážení bude potřeba k nalezení falešné mince?
Možná budete muset provést několik vážení, abyste našli odpověď. Výzva o 27 mincích je klasickým úkolem váhových hádanek, který vyvolává důležitou otázku: jak najít nejmenší počet vážení, abyste identifikovali falešnou minci mezi 27 mincemi pomocí závaží pouze třikrát?
Na první pohled se úkol může zdát poměrně složitý, ale při použití správného přístupu se řeší poměrně snadno. Je nutné správně uspořádat vážení, aby bylo možné nakonec jednoznačně identifikovat falešnou minci. Dodržováním určité strategie a prováděním vážení v určité sekvenci lze úkol zvládnout za tři vážení.
Mince, jedna falešná: kolik vážení potřebujete?
Jednou z účinných metod řešení tohoto problému je použití binárního vyhledávání. Za tímto účelem jsou mince rozděleny do 3 skupin: 9 mincí na každý šálek vah a zbývajících 9 mincí ponecháno stranou.
1. Nejprve se porovnají dvě skupiny po 9 mincích. Pokud jsou váhy stejné, pak je falešná mince mezi 9 zbývajícími mincemi.
2. Pokud se nepodařilo určit skupinu, ve které se Falešná mince nachází, dvě skupiny po 9 mincích jsou rozděleny do 3 skupin po 3 mincích.
3. Váží se dvě skupiny po 3 mincích. Pokud jsou váhy stejné, falešná mince je mezi 3 zbývajícími mincemi.
4. Pokud se nepodařilo určit skupinu, ve které se Falešná mince nachází, dvě skupiny po 3 mincích jsou rozděleny do 3 skupin po 1 minci.
5. Váží se dvě skupiny po 1 minci ze zbývajících 3 mincí. Pokud jsou váhy stejné, falešná mince je mezi dvěma zbývajícími mincemi.
6. Pokud jedna ze skupin 3 mincí váží méně nebo více než druhá skupina, pak je falešná mince v této skupině.
Takže k nalezení falešné mince z 27 mincí budete potřebovat ne více než 3 Vážení na šálkových vahách.
| Krok | Skupina mincí | Vážení |
|---|---|---|
| 1 | Skupina 1: 9 mincovna | Levý šálek vs pravý šálek |
| 2 | Skupina 2: 9. | Levý šálek vs pravý šálek |
| 3 | Skupina 3: 9 mincovna | Levý šálek vs pravý šálek |
| 4 | Skupina 4: 3 mince | Levý šálek vs pravý šálek |
| 5 | Skupina 5: 3 mince | Levý šálek vs pravý šálek |
| 6 | Skupina 6: 1 mince | Levý šálek vs pravý šálek |
Rozdělení do tří skupin
V této metodě je původních 27 mincí rozděleno do tří skupin po 9 mincích v každé. Váhy lze také použít k vážení dvou z těchto tří skupin.
Pokud jsou váhy vyvážené, znamená to, že falešná mince je mezi zbývajícími 9 mincemi, což znamená, že bude nalezena v dalším kroku.
Pokud váhy nejsou vyvážené, znamená to, že falešná mince je v jedné z těchto dvou skupin. V tomto případě je vybrána lehčí skupina dvou a její mince jsou rozděleny do tří skupin po 3 mincích v každé.
Po vážení dvou ze tří skupin lze určit, ve které z nich je falešná mince. Dále lze váhy opět použít k vážení dvou mincí z této skupiny.
Pokud jsou váhy vyvážené, znamená to, že falešná mince je třetí mincí z této skupiny. Pokud váha není vyvážená, znamená to, že falešná mince je jednou ze dvou mincí odebraných k vážení.
Pomocí této metody je tedy možné identifikovat falešnou minci v několika jednoduchých krocích vážení.
Vážení prvních dvou skupin
K vyřešení tohoto problému je třeba rozdělit všechny mince do tří stejných skupin po 9 mincích v každé. Pak je třeba zvážit dvě ze tří skupin.
Pokud jsou obě skupiny na vahách stejné, znamená to, že falešná mince je ve třetí, nevážené skupině. Dalším krokem je pak zvážit dvě mince z této skupiny mincí. Pokud je jedna z nich lehčí, je to falešná mince. Pokud jsou v rovnováze, pak je falešná mince třetí mincí, která zůstává nevážená.
Pokud je na váze jedna ze skupin lehčí, pak je falešná mince právě v této skupině. Chcete-li zjistit, která z mincí je falešná, musíte zvážit dvě jakékoli mince z této skupiny. Pokud je jedna z nich lehčí, je to falešná mince. Pokud jsou v rovnováze, pak je falešná mince třetí mincí, která zůstává nevážená.
Výběr nové skupiny
K určení falešné mince z 27 mincí je třeba použít metodu vážení na šálcích. Původně měly být všechny mince rozděleny do tří skupin po 9 mincích.
Dále se provádějí dvě vážení:
1. Váží se ramena vah, na jednom je 9 mincí a na druhém 9 mincí. Toto první vážení umožňuje určit,která ze dvou skupin mincí je falešná.
2. Skupina, ve které je falešná mince, je rozdělena do 3 stejných podle počtu mincí skupiny: 3 mince v každé. Dále se provádí nové vážení: jedna je položena na jednu skupinu mincí a druhá na druhou. Pokud jsou váhy opět stejné, pak je falešná mince ve zbývající skupině.
Po dvou vážení bude známo, ve které skupině je falešná mince. Pro přesné určení padělku je nutné zbývající skupinu rozdělit do tří mincí.
Třetí vážení určí, která ze tří mincí je falešná. V důsledku toho budou k určení falešné mince ve skupině 27 mincí potřeba pouze tři vážení na šálkových vahách.
Vážení nové skupiny
Vezmeme dvě ze tří skupin, které jsme dostali, a dáme 3 mince na levou a pravou misku vah. Pokud jsou váhy vyvážené, znamená to, že falešná mince je ve třetí skupině, kterou v tomto vážení nepoužíváme. Nyní zbývá pouze provést další vážení v této skupině, aby bylo možné určit konkrétní falešnou minci.
Pokud váhy nejsou vyvážené, znamená to, že falešná mince je v jedné ze dvou vybraných skupin. Vezmeme tuto skupinu a rozdělíme ji na 3 mince, které položíme na levou misku vah, a 3 mince na pravou misku vah. Pokud jsou váhy vyvážené, pak je falešná mince čtvrtou mincí, která zůstává nevyužita. Pokud váhy nejsou vyvážené, pak je falešná mince na misce vah, která je nižší. Nyní zbývá provést další vážení se dvěma mincemi z této misky vah, aby se identifikovala falešná mince.
Výběr složení poslední skupiny
Po provedení dvou vážení máme 3 skupiny mincí: dvě skupiny po 9 mincích a jednu skupinu 8 mincí. Už víme, že v jedné z těchto skupin je falešná mince.
K určení falešné mince musíme provést poslední vážení. Vzhledem k omezenému počtu vážení však nemůžeme jednoduše porovnat 9 mincí v každé skupině a snadno identifikovat falešnou.
Abychom snížili počet vážení, můžeme zvolit složení poslední skupiny tak, aby potřeba dalších vážení byla minimální. V tomto případě má smysl vážit 3 mince ze dvou skupin po 9 mincích.
Vážíme tedy 3 mince z každé skupiny po 9 mincích. Možné jsou dva exody:
- Pokud jedna z vážení ukáže, že vážené skupiny jsou stejné hmotnosti, pak je falešná mince ve zbývající skupině 8 mincí. K určení falešné mince můžeme provést další vážení porovnáním 3 mincí ze zbývající skupiny.
- Pokud jedna z vážení ukáže, že vážené skupiny nejsou stejné hmotnosti, pak je falešná mince v jedné ze suspendovaných skupin. Pro určení falešné mince můžeme provést další vážení mezi 3 mince z lehké skupiny.
Výběrem složení poslední skupiny s minimálním počtem možných dalších vážení tedy budeme schopni identifikovat falešnou minci v daném úkolu.
Vážení poslední skupiny
Po zjištění falešné mince v předchozím vážení zbývá najít ji mezi třemi mincemi v poslední skupině. K tomu je nutné provést další vážení.
Zbývající tři mince rozdělíme do dvou skupin po dvou mincích v každé. Jednu minci dáme na váhy na jedné straně a druhou minci na váhy na druhé straně. V tomto případě jsou možné dva výsledky:
- Váhy ukážou stejnou váhu. To znamená, že zbývající třetí mince je falešná.
- Váhy ukážou různou váhu. Pokud jedna strana váhy klesne, znamená to, že falešná mince je na této straně. A pokud jsou oba přívěsky na stejné úrovni, znamená to, že falešná mince je na třetí váze.
Tímto způsobem lze pomocí pouhých tří vážení přesně určit falešnou minci mezi 27 mincemi.
Identifikace falešné mince
V úkolu s 27 mincemi, ve kterém je jedna falešná, je nutné identifikovat falešnou minci vážením. Pro tento úkol budeme muset použít váhy.
Proces identifikace falešné mince lze popsat následovně:
- Rozdělíme 27 mincí do tří skupin po 9 mincích.
- Vážíme první dvě skupiny. Pokud váží stejně, znamená to, že falešná mince je ve třetí skupině.
- Pokud jedna z prvních dvou skupin váží méně, pak je falešná mince v jedné z nich. V tomto případě přejdeme k dalšímu kroku.
- Vybranou skupinu rozdělíme na tři části: na každou 3 mince.
- Vážíme dvě ze tří částí. Pokud váží stejně, pak je falešná mince ve třetí části.
- Pokud jeden ze dvou vybraných kusů váží méně, pak je v něm falešná mince. V tomto případě přejdeme k dalšímu kroku.
- Vezmeme vybranou část složenou ze 3 mincí a vážíme z ní jednu minci.
- Pokud jedna z vážených mincí váží méně, je tato mince falešná. Pokud všechny mince váží stejně, pak falešná mince v tomto úkolu chybí.
K identifikaci falešné mince z 27 mincí tak budou potřeba pouze tři vážení.