Myrkytetty viinipullo

Kuva: Che. Lisenssi: CC-BY-SA 2.5.

Kaukaisen maan kuninkaalla on viinikellarissaan 1000 pulloa erinomaisen hyvää viiniä. Kuningas viettää pian syntymäpäiviään ja pullot on varattu tarjoiltavaksi kutsuvieraille.

Kuningas on mielipuolisten tempaustensa vuoksi erittäin epäsuosittu ja hänen vastustajansa ovatkin onnistuneet myrkyttämään yhden viinipulloista. Kuninkaan vartiokaarti on kuitenkin saanut asiasta vihiä.

Myrkky on niin tehokasta, että pienen pieni pisara riittää tappamaan ihmisen. Myrkyn oireet alkavat näkyä kuitenkin vasta 22 tunnin kuluttua. On enää tasan vuorokausi aikaa kutsuvierasjuhlien alkuun, eikä kuningas halua peruuttaa juhlia, joten hän päättää selvittää maistajien avulla mikä pulloista sisältää myrkkyä.

Kuningas keksii tavan, jossa tarvitaan vain pieni joukko maistajia, mutta saadaan varmuudella ennen juhlien alkua selville mikä pulloista on myrkytetty. Mikä on tuo keino ja miten monta maistajaa tarvitaan?

Pieni määrä maistajia riittää, jos kukin maistajista maistaa useammasta pullosta ja kunkin maistajan pullot valitaan sopivasti niin, että kun useampi saa myrkytysoireita, voidaan päätellä mistä pullosta he kaikki ovat maistaneet.

Käytetään apuna binäärilukuja. Binääriluku koostuu ykkösistä ja nollista. Binääriluvun voi tulkita desimaaliluvuksi siten, että oikealta lukien ensimmäinen numero merkitsee ykköstä, toinen kakkosta, kolmas nelosta, neljäs kahdeksaa, viides kuuttatoista, kuudes kolmeakymmentäkahta jne. eli yleisemmin sanoen n:s numero merkitsee kakkosen n:ttä potenssia. Jos binääriluvun n:s numero on ykkönen, lisätään desimaalilukuun 2ⁿ. Esimerkiksi binääriluku 0000000101 on desimaalilukuna 1 + 4 eli 5. Binääriluku 0001100110 on desimaalilukuna 2 + 4 + 32 + 64 eli 102.

Numeroidaan viinipullot yhdestä tuhanteen binääriluvuilla. Sitten otetaan kymmenen maistajaa ja numeroidaan heidät ykkösestä kymmeneen. Maistaja numero 1 maistaa kaikista niistä viinipulloista, joiden binäärilukuesityksessä ensimmäinen numero on ykkönen. Maistaja 2 maistaa kaikista niistä viinipulloista, joiden toinen numero on ykkönen, ja niin edelleen. Kymmenen maistajaa riittää, koska kaikki luvut yhdestä tuhanteen voidaan esittää kymmennumeroisena binäärilukuesityksenä.

Desimaaliluku 1 on binäärilukuna 0000000001, joten vain ensimmäinen maistaja maistaa ensimmäisestä pullosta. Desimaaliluku 1000 on binäärilukuna 1111101000, joten viimeisestä pullosta maistavat maistajat 4, 6, 7, 8, 9 ja 10. Pullosta 329 eli binäärilukuna 0101001001 maistavat maistajat 1, 4, 7 ja 9.

Kun osa maistajista saa oireita, voidaan heti päätellä mistä pullosta he kaikki ovat maistaneet. Esimerkiksi jos maistajat 1 ja 3 saavat oireita mutta muut ovat terveitä, on pullo 0000000101 myrkytetty. Jos 2, 3, 6 ja 7 saavat oireita, on pullo 0001100110 myrkytetty.

Tällä tavalla tarvitaan pieni määrä maistajia, mutta toisaalta suurimmassa osassa tapauksista useampi kuin maistajista menehtyy. Jos maistajia olisi tuhat ja kukin maistaisi vain yhdestä pullosta, vain yksi maistaja menehtyisi.