Vergiftigde wijn
Vergiftigde wijn
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?
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?
Re: Vergiftigde wijn
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).
de bloedtesten kunnen nog efficienter, zie:
http://projecteuler.net/problem=352
(alleen svp hier geen volledige uitwerkingen/oplossingen van dit probleem plaatsen).
Re: Vergiftigde wijn
als een gevangene een fles wijn drinkt, drinkt hij die dan volledig uit?
Given that, by scientifical reasons, the state of an object is completely determined by the physical influence of its environment, the probability to roll six with a dice is either one or zero.
Re: Vergiftigde wijn
Nee, een slokje is voldoende. Zodat als de fles niet vergiftigd is de koning later de rest kan opdrinken.barto schreef:als een gevangene een fles wijn drinkt, drinkt hij die dan volledig uit?
-
- Vergevorderde
- Berichten: 1144
- Lid geworden op: 21 jan 2006, 15:09
- Locatie: Krimpen aan den IJssel
Re: Vergiftigde wijn
`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 gevangenen nodig, en kost het maar 1 maand.
Het bloedtest probleem is een heel ander probleem.
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 gevangenen nodig, en kost het maar 1 maand.
Het bloedtest probleem is een heel ander probleem.
``Life is complex. It has real and imaginary parts.''
Re: Vergiftigde wijn
Sjoerd Job schreef:
Op deze manier heb je gevangenen nodig, en kost het maar 1 maand.
maar de redenering is correct.
-
- Vergevorderde
- Berichten: 1144
- Lid geworden op: 21 jan 2006, 15:09
- Locatie: Krimpen aan den IJssel
Re: Vergiftigde wijn
typefout.wnvl schreef:Sjoerd Job schreef:
Op deze manier heb je gevangenen nodig, en kost het maar 1 maand.
maar de redenering is correct.
``Life is complex. It has real and imaginary parts.''
Re: Vergiftigde wijn
Als je deze techniek 'straight forward' toepast, dan krijg je:
het aantal slaven dat hij nodig heeft om de test uit te voeren is
Er is echter een manier om het aantal slachtoffers te beperken tot maximaal 8!!!
Niet echt moeilijk, maar wel een leuke (en levensreddende) variant
het aantal slaven dat hij nodig heeft om de test uit te voeren is
Er is echter een manier om het aantal slachtoffers te beperken tot maximaal 8!!!
Niet echt moeilijk, maar wel een leuke (en levensreddende) variant
-
- Vergevorderde
- Berichten: 1144
- Lid geworden op: 21 jan 2006, 15:09
- Locatie: Krimpen aan den IJssel
Re: Vergiftigde wijn
Bedoel je hier een binary search?Jánošík schreef:Als je deze techniek 'straight forward' toepast, dan krijg je:
het aantal slaven dat hij nodig heeft om de test uit te voeren is
Er is echter een manier om het aantal slachtoffers te beperken tot maximaal 8!!!
Niet echt moeilijk, maar wel een leuke (en levensreddende) variant
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.
``Life is complex. It has real and imaginary parts.''
Re: Vergiftigde wijn
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:
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.
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
...
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.
Given that, by scientifical reasons, the state of an object is completely determined by the physical influence of its environment, the probability to roll six with a dice is either one or zero.
Re: Vergiftigde wijn
Inderdaad. Met 10 bits zijn er 1013 getallen die maximaal 8 enen bevatten! Hij mag dus zelfs nog 13 flessen meer in zijn kelder hebbenbarto schreef:...dan kun je nog altijd elke fles identificeren maar er zijn geen nummers die in de binaire notatie meer dan 8 enen bevatten.
Re: Vergiftigde wijn
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?
maar waarom gemakkelijk maken als het moeilijk ook kan?
Given that, by scientifical reasons, the state of an object is completely determined by the physical influence of its environment, the probability to roll six with a dice is either one or zero.
Re: Vergiftigde wijn
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
Het ging me gewoon om het princiepe van maximaal 8 enen; hoe je het toepast... daar val ik niet over
Re: Vergiftigde wijn
1013 is het maximum aantal flessen die je met 10 man kan testen als er maar 8 mogen sterven.
-
- Vergevorderde
- Berichten: 1144
- Lid geworden op: 21 jan 2006, 15:09
- Locatie: Krimpen aan den IJssel
Re: Vergiftigde wijn
Ik had eerder over `het aantal slachtoffers' heen gelezen, maar ik realiseerde mij vannacht het volgende:Jánošík schreef:Als je deze techniek 'straight forward' toepast, dan krijg je:
het aantal slaven dat hij nodig heeft om de test uit te voeren is
Er is echter een manier om het aantal slachtoffers te beperken tot maximaal 8!!!
Niet echt moeilijk, maar wel een leuke (en levensreddende) variant
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. .
``Life is complex. It has real and imaginary parts.''