Viiniä kuninkaan juhliin – ratkaisu

Kuninkaalla oli suuret syntymäpäiväjuhlat tulossa. Hän oli varannut juhlia varten 1000 tynnyrillistä viiniä kellariinsa. Mutta viikkoa ennen juhlia alkoi hovissa levitä huhu, että yksi tynnyreistä olisi myrkytetty. – – Kuningas päättää testata viinikellarinsa ministereillään. Mikä on vähin määrä ministereitä, joka kuninkaan on uhrattava, jotta hän varmasti saisi selville, mikä tynnyreistä on myrkytetty?

Kuten aiemmassa ongelmassa mainittiin, on binääriluvuilla lukuisia sovelluksia. Myös tämä ongelma ratkeaa lukujen muuttamisella binäärijärjestelmään. Kertauksen vuoksi: luvun binääriesityksellä tarkoitetaan luvun esittämistä kakkosen potenssien avulla. Näin siis esimerkiksi 13=1\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0=1101_2. Koska 2^9=512 ja 2^{10}=1024, ongelma voidaan ratkaista vähimmillään kymmenen ministerin avustuksella.

Liitetään jokaiseen tynnyriin yksilöllinen 10-bittinen binääriluku; lisätään tarvittaessa luvun eteen nollia. Esimerkiksi 6. tynnyri olisi 0000000110 ja 789. tynnyri 1100010101. Tämän jälkeen järjestetään ministerit järjestykseen ensimmäisestä kymmenenteen. Tynnyrin binääriluvun bitti (1 tai 0) kertoo, pitääkö kunkin ministerin maistaa tynnyristä vai ei. Tässä esimerkiksi ensimmäinen ja toinen ministeri eivät maistaisi 6. tynnyristä, mutta maistaisivat 789. tynnyristä. Kolmannen ministerin ei tarvitsisi maistaa kummastakaan, kun taas esimerkiksi tynnyristä numero 245 (eli binäärisenä 0011110101) hän maistaisi, kuten myös neljäs, viides, kuudes, kahdeksas ja kymmenes ministeri.

One thought on “Viiniä kuninkaan juhliin – ratkaisu

  1. Jatkokysymys: Kuningas ei halua menettää kaikkia kymmentä ministeriään, vaan haluaa pitää mahdollisimman monta heistä hengissä. Mikä on vähin maksimimäärä kuolonuhreja kokeessa kymmenellä ministerillä ja kuinka se saavutetaan?

Vastaa

Sähköpostiosoitettasi ei julkaista. Pakolliset kentät on merkitty *

This site uses Akismet to reduce spam. Learn how your comment data is processed.