Medzi deviatimi mincami sú 4 falošné. Falošná minca je o 1 gram ťažšia ako pravá alebo o 1 gram ľahšia ako pravá. Falošné mince sú buď všetky ľahšie alebo všetky ťažšie. Inak sú mince rovnaké. Označím jednu mincu.
Máte rovnoramenné váhy, ktoré ukazujú rozdiel hmotností. (Ak je na jednej strane 5g a na druhej 12g, tak ukážu 7. Ak 9g a 2g, tak ukážu tiež 7 – na druhú stranu). Na koľko meraní zistíte a ako zistíte, či bola označená falošná alebo pravá minca?
Nápoveda
Stačí jediné váženie.
Riešenie
Neoznačené mince rozdelíme po 4 a dáme na váhy.
- Uvažujme, že bola označená pravá minca. Ak by sa nám podarilo dať na každú stranu 2 pravé a 2 falošné mince, tak by bol rozdiel 0. Vymeňme dve mince, ak sú rovnaké nič sa nezmení. Ak by sme vymenili pravú a falošnú mincu, tak na jednej strane stúpne hmotnosť o 1g a na druhej klesne o 1g. Rozdiel bude 2. Následne môžme prehadzovať mince ľubovoľne, rozdiel sa nezmení alebo sa zmení sa o 2.
- Uvažujme, že bola označená falošná minca. Nech sa nám podarilo dať na ľavú stranu 4 pravé a na pravú stranu 1 pravú s tromi falošnými. Ak sú ťažšie pravé mince bude rozdiel 3. Ak sú ťažšie falošné mince, tak bude rozdiel 3 na druhej strane. Následne môžme prehadzovať mince ľubovoľne, rozdiel sa nezmení alebo sa zmení sa o 2.
Preto stačí jedno váženie. Po 4 neoznačené mince na každú stranu váh. Ak je rozdiel párny, tak je označená pravá minca. Ak je rozdiel nepárny, tak je označená falošná.
Úvaha funguje pre ľubovoľný nepárny počet mincí.