En konge holder en fest med 1000 flasker vin. Nogen giver en flaske vin gift med gift, der ikke viser tegn, men 3 uger senere dør de. Hvordan finder kongen ved hjælp af 10 tjenere den forgiftede flaske vin før festen?


Svar 1:

Uanset hvor klog kongen er, kan han ikke finde den forgiftede vin og stadig tjene den gode vin ved blot at teste al vin på hans tjenere.

Den traditionelle strategi fungerer ikke.

For at prøve en flaske skal den åbnes. Bordsvin varer kun 3–5 dage efter åbning, før den går dårligt (hvidvin mindre, rødvin længere; juster efter type vin). Hvis kongen føder unikke kombinationer af prøver fra hver flaske til hver tjener og udleder hvilken flaske, der blev forgiftet af hvilken kombination af tjenere, der dør, vil det stadig tage tre uger at finde ud af, hvilken flaske der blev forgiftet - og da vil al vin have gået dårligt og bliver helt uegnet til at servere ved et kongebord.

Hvis vi ignorerer ødelæggelse og forsøger at minimere den tid, det tager at identificere den forgiftede flaske,

den bedste løsning er at fodre en unik kombination af dråber fra flaskerne vin til hver tjener. Nummer flaskerne i binær, og tildel hver tjener et sted i de resulterende ti-cifrede binære numre. For hver flaske, hvis en tjeners ciffer er 1, fod ham et dråbe fra den flaske; Hvis det er 0, skal du ikke gøre det. 2 ^ 10 binære tal svarer til 1024 unikke kombinationer mulige, nok til at registrere den forgiftede flaske, som kombination af tjenere dør ved. Men dette vil sandsynligvis dræbe fem tjenere (skønt det kunne dræbe så få som nul eller så mange som otte, hvis du antager, at du minimerer antallet af dødsfald ved at springe alle binære tal over med 9 tal og nogle af dem med 8 sådanne, som du kan gøre, fordi du har 24 ekstra kombinationer at lege med). Endelig resultat: 3 uger for at finde giften; cirka 5 dødsfald.

Hvis vi ikke ignorerer ødelæggelse, kan den forgiftede flaske findes inden for fem dage

hvis forgifteren åbnede vinen for at tilføje giften; derefter virker ødelæggelse i kongens favør. Enhver flaske, der er åbnet, går dårligt om 3-5 dage; så i stedet for at bruge sine tjeners liv, skulle kongen bruge sine tjeners næse: Lige før banketten skulle alle flasker åbnes, og flasken, der lugter som eddike, er den forgiftede. Endelig resultat: 5 dage for at finde giften; ingen dødsfald.

Denne strategi fungerer kun, hvis der er tid nok før banketten til, at den åbnede flaske vin går dårligt. Hvis de ikke har tid nok til at vente på, at den forgiftede flaske ødelægges, eller hvis ingen af ​​flaskerne er gået dårligt (fordi vinen blev forgiftet før tappning, pasteuriserede gifteren vinen efter tilsætning af giften eller selve giften dræbt alle mikroorganismer), skal kongen smide al vin væk og enten købe en ny batch eller forberede sig på at blæse om at være blevet en teetotaler.

Hvis vi ignorerer ødelæggelse og forsøger at minimere tabet af liv

, den bedste løsning er denne: Kongen nummererer flaskerne og tildeler 100 flasker til hver tjener; derefter drikker hver tjener et dråbe fra hver af 100 flasker. En time senere passerer hver tjener det højest nummererede af deres 100 flasker til den næste tjener; i slutningen af ​​linjen lægger den sidste tjener deres højeste nummererede flaske til side. Gentag, indtil den første tjener kun har en flaske tilbage, som han ikke behøver at prøve.

Ved udgangen af ​​de tre uger + 100 timer er det sandsynligt, at to tjenere er døde med en times mellemrum. Ved tidspunktet for, hvornår de døde, vil du vide, hvilken flaske de drak af, fordi det er den, der blev overgået fra den første døde tjener til den anden mellem det tidspunkt, de begge drak af den, nøjagtigt tre uger tidligere. 1/10 af tiden, vil kun en tjener dø, fordi den forgiftede flaske lå i den sidste tjeners 100 flasker og blev afsat i stedet for at blive sendt videre; vi ved, hvilken flaske det er ved tidspunktet for den sidste tjeners død. Hvis vi er ekstremt heldige, og flaske nr. 1 er den forgiftede, dør ingen overhovedet. Endelig resultat: 3 uger + op til 100 timer for at finde giften; 1,9 dødsfald.

Hvis vi ikke ignorerer ødelæggelse, men ikke kan bruge den til at identificere den forgiftede flaske, og kongen bekymrer sig kun om at identificere uåbnede, sikre flasker vin,

den bedste strategi er en binær søgning, og vi har kun brug for en tjener (skønt denne tjener 99,9% sandsynligvis dør). Del vinen i to; lad en tjener prøve halvdelen af ​​flaskerne og kasser dem derefter; lad den anden halvdel være uåbnet. Hvis tre uger senere dør tjeneren, er de andre 500 flasker i sikkerhed. Ellers deler vi de 500 flasker i halvdele og får tjeneren til at drikke fra 250 af dem; hvis tjeneren dør, er de andre 250 uåbnede flasker i sikkerhed. Fortsæt, indtil du kun har en uåbnet flaske tilbage (som er den forgiftede, og din tjener lever, selvom du nu ikke har nogen uspoleret vin), eller indtil din tjener dør, og du ved, at den forgiftede flaske er blevet åbnet. Endelig resultat: I gennemsnit 9 uger, men op til 90 uger, for at finde giften; 99,9% risiko for 1 død.

Realistisk set har kongen flere problemer end bare en forgiftet flaske vin og mangel på samvittighed. Hans tjenere vil gøre oprør, og folk vil vide bedre end at have tillid til ham. Da han har besluttet at risikere sine tjeneres liv i stedet for blot at teste vinen på rotter eller kaste den helt ud, kan forgifteren sandsynligvis give et meget godt argument for at ville slippe af med en sådan kald mand.


Svar 2:

Trin 1: Lad hver tjener drikke en prøve fra 90 flasker.

A: Ingen dør, det er nede på 100 mistænkte flasker, og du har stadig 10 ansatte. Hver tjener drikker vin fra 9 flasker.

a: Ingen dør. Vi er nede på 10 flasker med 10 tjenere. Brug kun 9 tjenere. En hver for at finde giften, hvis alle lever, er det den resterende flaske …… ...

b: En tjener dør. Vi har 9 tjenere og 9 flasker. En hver

B: En tjener dør, vi har nu 90 mistænkte flasker og 9 tjenere. Hver drikker fra 9 flasker.

c: Ingen dør. Vi har nu 9 flasker og 9 tjenere. En hver.

d: En dør. 9 flasker og 8 tjenere tilbage. Hver tjener drikker fra en flaske, en reserveret. Hvis ingen dør, er det den sidste flaske.