Mám štyri na pohľad rovnaké guličky, pričom s istotou viem, že práve jedna z nich je buď ľahšia alebo ťažšia v porovnaní so zvyšnými tromi, ktoré majú presne rovnakú hmotnosť. Máme k dispozícii dvojmiskovú elektronickú váhu, ktorá vie oznámiť len dva rôzne výsledky a to: "hmotnosť v miske naľavo je väčšia ako hmotnosť v miske napravo", alebo "hmotnosť v miske napravo je väčšia ako hmotnosť v miske naľavo". Ak sa na miskách vážia rôzne hmotnosti, odpovie váha zaručene správne. Ale ak sa vážia rovnaké hmotnosti, zvolí váha každú zo svojich dvoch možných odpovedí s pravdepodobnosťou 1/2. Našim cieľom je zistiť, ktorá z guličiek je odlišná od ostatných dvoch a či je ľahšia, alebo ťažšia. Môžeme však vykonať maximálne 3 váženia. Aký systém váženia by ste zvolili?
6 komentárov:
neviem ci tento postup bude
v sulade s pravidlami, ale
nikde sa nehovori ze by
bol zakazany :-D
(oznacme si gulicky 1234)
na jednu misku vah
dame gulicky
1 2
na druhu
3 4
Teraz urcite nie je
na oboch miskach rovnaka
vaha->jedna z nich je tazsia.
Zoberme lubovolnu gulicku z prvej
misky a lubovolnu z druhej a vymenme ich.
Ak
A.) sa zmenilo to, ktora miska je
tazsia, potom jedna z vymenenych
guliciek je urcite tazsia alebo (xor)
druha je lahsia.
Gulicky ktorymi sme nehybali
su rovnakej vahy.
Takze presunme tieto rovnake gulicky na
jednu misku, zvysne na druhu.
Potom uz podla toho, ktora
miska je tazsia lahko zistime
co potrebujeme.
B.) sa nezmenilo to, ktora
miska je tazsia, potom vymenene
gulicky boli urcite rovnake.
A urobime to iste co v A.) ->
dame rovnake gulicky na jednu misku.
Hmmm to mi ale vychadza na tri tahy...
podozrive... :O)
j: Výborne! (S tou štvorkou som sa jednoducho pomýlil; sorry. Opravím to.)
Kľúčom je skrátka vyhnúť sa váženiu dvojice guličiek, ktoré môžu mať rovnakú hmotnosť, lebo potom by sme nemohli znížiť po každom vážení entropiu na polovicu a teda 3 bity by sme neznížili na 0 bitov v troch váženiach. Táto úvaha už priamo napovedá, že by sme mali asi zakaždým vážiť všetky štyri guličky súčasne.
No, v príspevku píšem, že na vyriešenie tejto úlohy nie je treba matematické vzdelanie a potom v komentári spomínam nejakú entropiu. Takže vysvetlenie, čo som tým myslel v ľudskejšej reči: Na začiatku máme 8 možností; ak označíme ako L ľahšiu, T ťažšiu a R takú guličku, ktorá má hmotnosť ako niektoré dve iné, tak guličky 1234 môžu byť LRRR, RLRR, RRLR, RRRL, TRRR, RTRR, RRTR, RRRT. Každé naše váženie musí byť teda také, že zmenší priestor možností na polovicu.
Veľmi letmo a trochu nepresne: Neurčitosť (entropiu) môžeme vyjadriť v "bitoch" ako dvojkový logaritmus počtu všetkých možností(ak ich pripúšťame s rovnakou pravdepodobnosťou). To znamená, že v našom probléme je na začiatku neurčitosť 3 bity a na konci 0 bitov. Ak je váha taká, že dáva len dva výsledky, tak nám môže poskytnúť najviac 1 bit informácie. Váha, ktorá dáva 3 možné výsledky (napríklad vie povedať, že obe hmotnosti sú rovnaké), nám každým vážením môže dať viac informácie.
Takýmito úvahami sa dá napríklad o niektorých úlohách ľahko ukázať, že sa NEdajú vyriešiť na zadaný počet vážení. Povedzme, že máme 10 guličiek, z ktorých je niektorých 5 ľahších (a pritom majú rovnakú hmotnosť) a zvyšných 5 je ťažších (a tiež majú rovnakú hmotnosť). Potom priestor stavov má 10 nad 5 prvkov a ak máme váhu, ktorá podáva 3 výsledky (ľahšie, ťažšie, rovnako ťažké), tak na presné určenie ktorých 5 je to tých ľahších, potrebujeme aj pri optimálnej stratégii niekedy aspoň log2(10 nad 5):log2(5)=5.03, čiže 6 vážení.
vdaka za tu ludsku rec. po tom prvom prispevku som sa trosku zhrozila, ze v tejto nocnej hodine zadrhnem zavity. :-) inak, fiiha. pekne pozadie ulohy. hned ma mohlo napadnut, ze nad gulickami asi len tak nerozmyslas. :-)
Rado: Pekná úloha.
Kedy Ťa vlastne napadlo vymýšľať vlastné? Koľko si ich už navymýšľal?
Anonymka: Váženia mi chodia po rozume z viacerých dôvodov; napríklad som si nedávno čítal príklad o váženiach z Gardnera, váženia súvisia s teóriu informácie, ktorú si teraz trochu pozerám a máličko aj s mojim seríóznym matematickým výskumom.
Inak podobné príklady ako je ten náš (a to aj bez náhodného výsledku) nie sú vôbec jednoduché. Napríklad minule som zachytil jeden pomerne nový článok vo veľmi slušnom matematickom časopise, ktorý (ten článok) podobný problémom rieši. Nezdá sa to, ale takéto úlohy môžu byť extrémne ťažké a zďaleka v tejto oblasti nie je všetko vyriešené.
Peter: Nuž, vlastné príklady vymýšľam akonáhle som začal cvičiť základy teórie pravdepodobnosti, čo je už neuveriteľných 10 rokov. Navymýšľal som ich už stovky (najmä z pravdepodobnosti), ale človek dodatočne väčšinou zistí, že čosi podobné sa už dávno riešilo a vyriešilo. Pár príkladov je však takých, o ktorých (zatiaľ) neviem, že by ich už niekto formuloval.
Zverejnenie komentára