On pellettejä ja pellettejä

 

Colin Palmer. Lisenssi: CC-BY

Aiemmin kaupan apulainen sai tehtäväkseen erotella liian kevyet lasikuulat normaaleista lasikuulista. Tällä kertaa kaupan varastoon on tuotu kymmenen tynnyriä täynnä pellettejä. Osassa tynnyreistä on 1 gramman ja osassa 2 gramman painoisia pellettejä. Kukaan ei tiedä missä tynnyreissä on kevyitä ja missä painavia pellettejä.

Apulaisella on käytössään tarkka digitaalinen painovaaka. Hän saa tehtäväkseen selvittää vaa'an avulla mitkä tynnyrit sisältävät painavampia pellettejä, mutta vaakaa saa käyttää vain yhden ainoan kerran.

Millä tavalla tehtävä suoritetaan?

Aikaisemmassa tehtävässä tiedettiin, että vain yksi laatikko sisälsi eripainoisia kuulia. Tällä kertaa painavia pellettejä voi olla yhdessä tai useammassa tynnyrissä, tai ei yhdessäkään. Tynnyrit voi kuitenkin erotella toisistaan lähes samaan tapaan kuin aikaisemmin laatikot.

Merkitään tynnyrit numeroilla yhdestä kymmeneen. Poimitaan ensimmäisestä tynnyristä 1 pelletti, toisesta 2 pellettiä, kolmannesta 4, neljännestä 8, viidennestä 16 jne. Tynnyristä i otetaan siis 2^(i-1) pellettiä. Kerättyjen pellettien yhteispaino mitataan vaa'alla.

Jos kaikissa tynnyreissä olisi yhden gramman painoisia pellettejä, yhteispainoksi tulisi 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 = 1023 grammaa. Siitä miten paljon mitattu yhteispaino eroaa 1023:sta voidaan päätellä mitkä tynnyrit sisältävät painavampia pellettejä.

Binäärilukuja tunteville em. kahden potenssit ovat tuttuja. Mainituilla luvuilla on se ominaisuus, että niitä valikoiden yhteenlaskemalla voidaan muodostaa jokainen luku väliltä 1 - 1023, mutta kukin luku on mahdollista muodostaa vain yhdellä tavalla. Ongelman ratkaisuna on siis hajottaa mitattu erotus osiinsa, jolloin osat kertovat suoraan, mitkä tynnyrit sisältävät painavia pellettejä.

Esimerkiksi jos yhteispaino on 1025 grammaa, on erotus 2 grammaa, joten ainoastaan tynnyrissä kaksi oli painavampia pellettejä. Jos yhteispaino on vaikkapa 1060 on erotus 37, joka muodostuu luvuista 1 + 4 + 32, eli tynnyreissä 1, 3 ja 6 on oltava painavampia pellettejä.