Vergiftigde wijn

[wnvl]

Onderstaande vraag over het mengen van bloed deed mij denken aan dit raadsel.

viewtopic.php?f=5&t=7108

Een slechte koning heeft 1000 flessen wijn. Een naburige koningin wil de koning vermoorden. Ze stuurt een dienaar uit om de wijn van de koning te vergiftigen. De bewaker betrapt de dienaar op het ogenblik dat hij nog maar 1 fles heeft vergiftigd. De bewaker weet niet welke fles vergiftigd is, maar hij weet dat het gif zo sterk is dat zelfs als het verdund wordt, nog altijd dodelijk is.

Bovendien treedt de dood pas in na 1 maand. De koning beslist een aantal van zijn gevangenen uit de kerker wijn te laten drinken. In plaats van 1000 gevangenen op te offeren, weet hij dat 10 gevangenen volstaan om uit te vissen welke wijn vergiftigd is en bovendien kan hij de rest van de wijn binnen de 5 weken opdrinken. Hoe moet hij dit aanpakken?

[siep]

Omdat je volgens mij ook wel van Euler-problemen houdt:
de bloedtesten kunnen nog efficienter, zie:
http://projecteuler.net/problem=352
(alleen svp hier geen volledige uitwerkingen/oplossingen van dit probleem plaatsen).

[barto]

als een gevangene een fles wijn drinkt, drinkt hij die dan volledig uit?

[wnvl]

als een gevangene een fles wijn drinkt, drinkt hij die dan volledig uit?

Nee, een slokje is voldoende. Zodat als de fles niet vergiftigd is de koning later de rest kan opdrinken.

[Sjoerd Job]

`denken':
geef elke fles een getal tussen 1 en 1000, en schrijf dit binair (10 cijfers lang).
laat gevangene 1 elke fles drinken die een 1 heeft op de eerste plek
laat gevangene 2 elke fles drinken die een 1 heeft op de tweede plek
...
laat gevangene 10 elke fles drinken die een 1 heeft op de 10e plek.

(uiteraard drinken ze maar een heel klein slokje).

Op deze manier heb je

\(\lfloor \log_2 1000\rfloor\)

gevangenen nodig, en kost het maar 1 maand.

Het bloedtest probleem is een heel ander probleem.

[wnvl]

Op deze manier heb je

\(\lfloor \log_2 1000\rfloor\)

gevangenen nodig, en kost het maar 1 maand.

\(\lceil \log_2 1000\rceil\)

maar de redenering is correct.

[Sjoerd Job]

Op deze manier heb je

\(\lfloor \log_2 1000\rfloor\)

gevangenen nodig, en kost het maar 1 maand.

\(\lceil \log_2 1000\rceil\)

maar de redenering is correct.

typefout.

[Ifit]

Als je deze techniek 'straight forward' toepast, dan krijg je:
het aantal slaven dat hij nodig heeft om de test uit te voeren is

\(\lceil \log_2 1000\rceil=10\)

Er is echter een manier om het aantal slachtoffers te beperken tot maximaal 8!!!

Niet echt moeilijk, maar wel een leuke (en levensreddende) variant

[Sjoerd Job]

Als je deze techniek 'straight forward' toepast, dan krijg je:
het aantal slaven dat hij nodig heeft om de test uit te voeren is

\(\lceil \log_2 1000\rceil=10\)

Er is echter een manier om het aantal slachtoffers te beperken tot maximaal 8!!!

Niet echt moeilijk, maar wel een leuke (en levensreddende) variant

Bedoel je hier een binary search?

Geef een slaaf een mix van 0..499, als hij leeft, geef hem 500..749, anders, geef een slaaf van 0..249
en zo voor kleinere intervallen?

Zo ja, dan werkt dit niet wegens je tijdslimiet.

[barto]

zowieso kunnen maximaal 9 slaven sterven want 1023=1111111111 (10 enen) komt niet voor.

bekijk de getallen die in hun binaire notatie meer dan 8 enen bevatten:

Code: Selecteer alles

511  =  111111111
767  = 1011111111
895  = 1101111111
959  = 1110111111
991  = 1111011111
1007 = 1111101111
1015 = 1111110111
1019 = 1111111011
1021 = 1111111101
1022 = 1111111110
1023 = 1111111111
...

die sla je over bij het nummeren omdat het potentiële 9-slaven-doders zijn:
Geef gewoon elk getal zijn binaire cijfer, maar vanaf 511 geef je elk getal de binaire notatie van het getal erna:
511=111111111 wordt 512=1000000000
512=1000000000 wordt 513=1000000001
enz..., tot en met 765. (want 766 dat zou 767 worden wat niet mag)

vanaf 766 sla je dan twee getallen over:
766=1011111110 wordt 768=1100000000
767=1011111111 wordt 769=1100000001
enz..., tot en met 892. (want 893 dat zou 895 worden wat niet mag)

enzovoort:
3 overslaan t.e.m. 959-4=955
4 overslaan t.e.m. 991-5=986
5 overslaan t.e.m. 1007-6=1001, maar t.e.m. 1000 volstaat al.

dan kun je nog altijd elke fles identificeren maar er zijn geen nummers die in de binaire notatie meer dan 8 enen bevatten.

[Ifit]

...dan kun je nog altijd elke fles identificeren maar er zijn geen nummers die in de binaire notatie meer dan 8 enen bevatten.

Inderdaad. Met 10 bits zijn er 1013 getallen die maximaal 8 enen bevatten! Hij mag dus zelfs nog 13 flessen meer in zijn kelder hebben

[barto]

Gemakkelijker zou zijn om gewoon die 5 flessen met 9 of 10 enen een nummer te geven van 1001 tot 1005.
maar waarom gemakkelijk maken als het moeilijk ook kan? 8)

[Ifit]

Zelf had ik bedacht om het nummeren te beginnen bij 0000000000. Kom je een getal tegen met 9 enen, dan sla je het gewoon over en je gaat verder met het volgende. Is ook niet erg moeilijk he

Het ging me gewoon om het princiepe van maximaal 8 enen; hoe je het toepast... daar val ik niet over

[wnvl]

1013 is het maximum aantal flessen die je met 10 man kan testen als er maar 8 mogen sterven.

\(2^{10}-\binom{10}{1}-\binom{10}{0}=1013\)

[Sjoerd Job]

Als je deze techniek 'straight forward' toepast, dan krijg je:
het aantal slaven dat hij nodig heeft om de test uit te voeren is

\(\lceil \log_2 1000\rceil=10\)

Er is echter een manier om het aantal slachtoffers te beperken tot maximaal 8!!!

Niet echt moeilijk, maar wel een leuke (en levensreddende) variant

Ik had eerder over `het aantal slachtoffers' heen gelezen, maar ik realiseerde mij vannacht het volgende:

het aantal nodige slaven is nog steeds 10, maar je weet dat ongeacht welke fles vergiftigd is, er hoogstens 8 slaven sterven. (op jou manier). Dus het aantal potentiele slachtoffers is 10, maar het potentiele aantal slachtoffers is 8. .