Hur Räddar Vi Kejsarens Fest?

Jag tror jag kommit på hur man löser det med endast 10 personer utifrån det här jag flummade om tidigare.

↗ till inlägget

Hmm. Om en person person dricker, varannan. Nästa person var fjärde, och nästa åttonde...

Vi använder oss av det binära talsystemet! För att representera talet 1000 behöver vi 10 bitar (2^10). Vi har alltså 10 personer här:

0000000000

Flaska nummer 712 i binärt är:

1011001000

Alltså ska fånge nummer 1, 3, 4 och 7 dricka denna flaskan. Om bara dessa dör men ingen annan vet vi att det är flaska nummer 712 som var förgiftad.

Vann jag?

Det där är fan genialt.

Tack.

Det roliga är att det helt omkullkastar vad Mezox precis sa i #20. Som max kan 9 fångar dö (om det är flaska 511) och metoden är ändå väldigt träffsäker. Säkerheten är helt oberoende av hur många som dör.

↗ till inlägget

Jag tror jag kommit på hur man löser det med endast 10 personer utifrån det här jag flummade om tidigare.

Vi använder oss av det binära talsystemet! För att representera talet 1000 behöver vi 10 bitar (2^10). Vi har alltså 10 personer här:

0000000000

Flaska nummer 712 i binärt är:

1011001000

Alltså ska fånge nummer 1, 3, 4 och 7 dricka denna flaskan. Om bara dessa dör men ingen annan vet vi att det är flaska nummer 712 som var förgiftad.

 

Vann jag?

Dave37: Det omkullkastar inte vad jag sa alls. Det jag sa var att de flesta fall ska leda till att ungefär hälften dör. Och detta är helt korrekt.

Vi räknar antal fall som ger ett x antal döda:

0 döda: 0 fall

1 död: 10 fall

2 döda: 45 fall

3 döda: 120 fall

4 döda: 210 fall

5 döda: 252 fall

6 döda: 209 fall

7 döda: 113 fall

8 döda: 36 fall

9 döda: 5 fall

10 döda: 0 fall

Sannolikheten att mellan 4-6 dör är alltså 67% medan sannolikheten att fler än 8 eller mindre än 2 dör är 1,5%. Den mesta sannolikheten är alltså koncentrerad i mitten. Om någon är intresserad av detta fenomen finns mer info här.

Sannolikheten att man dör med denna metod ligger liite under 50%. Hade man haft en tvåpotens antal flaskor hade sannolikheten varit 50% exakt.

WASD: Detta var förresten det du var inne på tidigare med binärsökning. Modifikationen jag syftade på var att man låter de följande fångarna "i förhand" smaka på flaskor så man får en typ av binärsökning.

Om man t.ex. har 8 flaskor så låter man fångarna smaka på följande sätt:

( x betyder att fången smakar o betyder att han inte smakar)

Fånge1: X X X X O O O O

Fånge2: X X O O X X O O

Fånge3: X O X O X O X O

Detta blir då en sorts binärsökning (det är förresten exakt det man gör när man använder det binära talsystemet). Fånge 1 bästämmer i vilken halva falskan ligger. Oavsett vilken halva man får kommer fånge 2 bestämma i vilken halva av den som giftet ligger och samma med fånge 3. Efter 3 halveringar får man bara en flaska kvar. Svaret blir alltså taket av 2-logaritmen av n, för n flaskor.

Är det någon som känner att de vill bevisa att det inte går med 9 fångar eller färre?

Hehe, en liten parentes. Mönstret du ritade upp med de olika fångarna påminner väldigt mycket om hur pi-orbitaler i konjugerade kolsystem bildas för olika energinivåer inom kemin, där fånge 1 symboliserar grundtillståndet, fånge två några energinivåer högre och fånge tre det högsta. Det finns en del energinivåer till emellan dem men det är för att man inom kemin räknar med -1, 0 och 1.

Jasså var det var det sättet du tänkte på när du sa att du löst det med mindre än 20 Mezox? Jag trodde att jag kom på det först :/

Med 9 fångar finns det inte tillräckligt med olika möjligheter för att representera alla 1000 flaskor så jag är väldigt säker på att det inte går mer mindre än 10.

↗ till inlägget

Jasså var det var det sättet du tänkte på när du sa att du löst det med mindre än 20 Mezox? Jag trodde att jag kom på det först :/

Jo det var den metoden jag tänkte på. När min vän gav mig problemet på facebook så gick mina tankar direkt till binära tal. Men du borde ändå vara väldigt stolt! Uppgiften är analog med en uppgift som har varit med i en nordisk matematiktävling (och det är ett fåtal gymnasielever i Sverige som kan lösa sådanna), och jag hade fördelen att jag var med året då den uppgiften gavs (det var faktiskt en av de få uppgifter på tävlingen som jag lyckade lösa!).

↗ till inlägget

Med 9 fångar finns det inte tillräckligt med olika möjligheter för att representera alla 1000 flaskor så jag är väldigt säker på att det inte går mer mindre än 10.

Vi kan kanske försöka lösa ett tillhörande problem:

Hur många fångar kan du som mest låta smaka på flaskorna utan att efter ett dygn kunna räkna ut vilken flaska som är giftig? Det antas att två olika fångar inte smakar på exakt samma urval av flaskor.

Två fångar får alltså smaka på samma flaska, men de får inte ha alla flaskorna de smakar på gemensamt (det måste finnas en flaska som en av de smakar på men inte den andra).

Hahaha folk verkar inte vara lika intresserade av att hittade den mest ineffektiva lösningen som att hitta den effektivaste.

Nä det här är inte riksdagen. ;)

↗ till inlägget

Hahaha folk verkar inte vara lika intresserade av att hittade den mest ineffektiva lösningen som att hitta den effektivaste.

Flest som behövs :P

Ja det skulle ju bli 1000 som smakar på en flaska var. Om man vill vara onödig kan man dra in 10000 och låta 10 personer smaka på samma flaska.

↗ till inlägget

Hur många fångar kan du som mest låta smaka på flaskorna utan att efter ett dygn kunna räkna ut vilken flaska som är giftig? Det antas att två olika fångar inte smakar på exakt samma urval av flaskor.

 

Två fångar får alltså smaka på samma flaska, men de får inte ha alla flaskorna de smakar på gemensamt (det måste finnas en flaska som en av de smakar på men inte den andra).

Gäller det att ska vara vara omöjligt i alla fall eller att det ska finnas åtminstone ett fall då det är omöjligt? Alla flaskor måste bli smakade på också eller?

1. Nej det behöver bara vara omöjligt för ett fall, märker nu att det inte är självklart av formuleringen :P

2. Alla flaskor behöver inte smakas på (tror dock inte det ändrar svaret, men jag kan ha fel).

Punkt nr 2 i mitt förra inlägg ger dessutom en hyfsad ledning till lösningen (tror jag? haha).

min gissning är att man kan använda minst 1141482039062610525124385499111575963796977943818514937767468775030412797373007720902532234021804456

964721881350925601949893776182038877736047485870797067515127 fångar och ändå inte säga vilken flaska som innehåller det förgiftade vinet.

Förklara gärna hur :D

kommer inte ihåg hur jag räknade, men typ nått sånt här tänkte jag:

man "tar bort" det förgiftade vinet så att man bara har 999 flaskor att smaka på.

Sen låter man 999 fångar smaka på var sin flaska. Sen kan man låta fångar smaka på två flaskor i olika kombinationer. då kan man lägga till en massa andra fångar, sen låter man fångar smaka på kombinationer av 3 flaskor osv. kommer inte ihåg hur jag räknade och jag tror jag gjorde fel men det lär bli ett extremt stort tal. Och jag tror det går att få fram ett ännu större tal om man blandar in den förgiftade flaskan också.