10. príklad - Vzorové riešenie

V riešení budeme predpokladať, že ľavá misa je vždy ťažšia ako tá pravá, pričom v prípade, že to tak nie je, bude váha ukazovať záporné číslo. Táto úprava úlohu nemení.

Najprv si ukážeme, že keď ľubovoľne mince rozdelíme do ľavej misy, pravej misy a mimo váhu, tak vždy budeme vedieť určiť, v ktorej skupinke sa nachádza každá minca. Ukážeme to tak, že číslo, ktoré ukáže váha, unikátne určí polohu každej mince. Teda žiadne dve rôzne rozpoloženia mincí neukážu rovnaké číslo.

Ukážeme si to sporom, takže nech existujú dve rôzne rozpoloženia mincí také, že ukážu rovnaké číslo. Číslo na váhe je súčet mincí na ľavej strane mínus súčet mincí na pravej strane, takže dostaneme:

​\pm 3^{\alpha_1} \pm 3^{\alpha_2} \pm \dots \pm 3^{\alpha_n} = \pm 3^{\beta_1} \pm 3^{\beta_2} \pm \dots \pm 3^{\beta_m}​

Pričom kladné členy sú na ľavej mise, záporné členy na pravej mise a pre exponenty platí: \alpha_1 < \alpha_2 < \dots < \alpha_n a \beta_1 < \beta_2 < \dots < \beta_m. 

Ak \alpha_1 \neq \beta_1, tak vieme obe strany predeliť 3^{\min(\alpha_1,\beta_1)} . Potom na jednej strane bude číslo deliteľné 3 a na druhej nebude deliteľné 3 takže dostávame spor a tým pádom \alpha_1 = \beta_1. Ďalej keď sa pozrieme na znamienka pri 3^{\alpha_1} a 3^{\beta_1}, tak ak by boli rôzne, tak by sme dostali:

2(\pm 3^{\alpha_1}) =\pm 3^{\alpha_2} \pm \dots \pm 3^{\alpha_n} \pm 3^{\beta_2} \pm \dots \pm 3^{\beta_m}

Kde po predelení 3^{\alpha_1} dostaneme, že 2 je rovné číslu deliteľnému 3, čo je spor. Takže dostávame, že 3^{\alpha_1} = 3^{\beta_1} a že majú rovnaké znamienko, takže v oboch rozdeleniach je minca s váhou 3^{\alpha_1} na rovnakej mise. 

Mincu s váhou 3^{\alpha_1}​ teda môžeme odobrať z oboch rozpoložení mincí a získať tým nové 2 rôzne rozpoloženia mincí s rovnakým číslom na váhe. Tento proces však môžeme opakovať, čím zistíme, že n = m a \alpha_k = \beta_k pre ľubovoľné k. To však ale znamená, že ak dve rozpoloženia majú rovnaké číslo na váhe, tak to musia byť rovnaké rozpoloženia mincí.

Zistili sme, že nech ľubovoľne rozdelíme mince na váhy, vždy vieme povedať o každej minci to, že či sa nachádza na pravej mise, ľavej mise, alebo mimo váhy. 

Teraz sa pozrime, na koľko ťahov vieme nájsť mincu s váhou 1. Každým vážením sa nám mince rozdelia na 3 skupiny a my o každej minci vieme povedať v ktorej skupine sa nachádza. Ak využijeme n vážení, tak každá minca dostane nejakú postupnosť dĺžky n skladajúcu sa z troch typov skupín, v ktorých sa daná minca nachádzala v danom vážení. Ak chceme jednoznačne identifikovať mincu s váhou 1, tak musí mať svoju postupnosť rôznu od všetkých ostatných. Lebo ak dve rôzne váhy mincí majú rovnakú postupnosť, znamená to, vždy boli na tých istých váženiach a nevieme ich od seba odlíšiť. 

Dvomi váženiami môžeme získať najviac 3^2 = 9 rôznych postupností, teda po dvoch váženiach sa nám môže stať, že minca s váhou 1 bude mať rovnakú postupnosť ako minca s inou váhou a teda ich nebudeme vedieť rozlíšiť.

Teraz ukážeme, že na 3 váženia vieme nie len nájsť, ktorá minca má váhu 1, ale dokonca aj váhy všetkých mincí. Ako sme vyššie ukázali, nájsť váhu niektorej mince je ekvivalentné s priradením danej minci unikátnu postupnosť. Máme 27 mincí a existuje 3^3=27 postupností dĺžky 3 rozdelenia do 3 skupín. Takže každej minci vieme priradiť jednu postupnosť a podľa týchto postupností vieme v ktorom vážení máme dať ktoré mince do ktorej skupiny.​

Odpoveď: Mincu s váhou 1 vieme nájsť na najmenej 3 váženia (popis ako je popísaný vyššie), váhy všetkých mincí vieme tiež nájsť na najmenej 3 váženia (popis ako je tiež popísaný vyššie).