Hur Räddar Vi Kejsarens Fest?

[Mezox]

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?

Jo det är den mest effektiva metod jag har hittat :D , bra gjort! Det går även att bevisa att det är den bästa metoden, alltså att det inte går att göra det med färre än 10 personer.

 

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?

[Dave37]

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.

[WASD]

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.

Redigerat 3 November 2012 av WASD

[Mezox]

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!).

 

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.

Japp det är det som är tanken. Om man har 9 fångar finns det 2^9 = 512 olika möjliga utfall som man kan få. Eftersom det finns hela 1000 olika fall för giftets placering måste det finnas flera olika "giftplaceringar" som ger samma utfall i död/icke-död hos fångarna. Och om giftets placering råkar va någon av dessa kan man inte urskilja den från den andra.

 

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).

[Mezox]

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

[Dave37]

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

[WASD]

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

Ineffektivaste som i att flest personer dör, eller att flest personer behövs? Ineffektivast i antal dagar som behövs kan man också undersöka.

[Mezox]

Flest som behövs :P

[WASD]

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.

[Mezox]

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).

Här är instruktionerna (två fångar får alltså inte smaka på exakt samma urval av flaskor). Och jag kan avslöja att man kan ha mer än 1000 fångar utan att kunna ta reda på vilken som är giftig. Redigerat 5 November 2012 av Mezox

[Dave37]

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?

[Mezox]

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).

Redigerat 5 November 2012 av Mezox