Hur Räddar Vi Kejsarens Fest?

[WASD]

Som sagt är festen imorgon, men du kanske kan anpassa din metod för det fallet?

Nepp. Min metod skulle då behöva 1000 personer på en gång.

[Mezox]

Jag kan nämna att jag har löst det på sätt som gör att mindre än 20 fångar krävs. Jag låter det stå lite öppet som det är nu och kommenterar som jag gjort hittils andras förslag.

 

WASD: Du kanske kan göra anpassningen på ett lite mer "kreativt" sätt. Det borde gå. :)

[Dave37]

Nepp. Min metod skulle då behöva 1000 personer på en gång.

Kejsarens metod är ett specialfall av din metod.

[WASD]

Hmm. Om en person person dricker, varannan. Nästa person var fjärde, och nästa åttonde... Eller om man istället för att dubblera går ett steg i taget, så kanske man på något sätt med en någorlunda liten mängd personer ser vilka som dör och komma fram till vilken flaska det var.

 

Det kanske är på något liknande sätt ni redan tänkt. Att man med en begränsad mängd personer som dricker vissa specifika flaskor kan beräkna vilken av flaskorna som var förgiftad genom att se vilka som dog.

 

Jag kom på att man kan göra såhär med 8 flaskor, om vi ställer upp dem såhär:

1 2 3

4 . 5

6 7 8

Så kan vi ha 4 personer som dricker varsin "kant". Alltså 1+2+3, 1+4+6, 6+7+8, 3+5+8. Där kan man räkna ut vilken flaska som var förgiftad beroende på vilka som dog. 4 personer för att undersöka 8 flaskor. Om man istället för en kvadrat såhär har en hexagon borde samma person fungera med 6 personer för 12 flaskor.

 

Eller om man istället har en 3x3 kub som alltså kan innehålla 20 flaskor i kanterna, på totalt 6 kanter. 6 personer för 20 flaskor. Man kanske kan dra iväg det här i ännu högre dimensioner. Hur många kanter och hörn har en "4D-kub"? Från 2D till 3D blev metoden effektivare. Allt detta kom jag på genom att ha läst ord som "dimensioner" och "sida av kuben" som ni nämnt tidigare. Så det är kanske detta ni sagt.

 

Ett annat sätt att rädda en kejsarens fest är att dra dit Dave som underhållare!

Redigerat 2 November 2012 av WASD

[Dave37]

WASD du upprepar det som mumutio redan har sagt, vi har redan löst problemet om man ställer upp flaskorna i en kub eller någon annan jämnsidig kropp vars vinklar mellan sidorna är 90 grader i valfri dimension mellan 1 och 10.

 

Med fyra dimensioner behöver man 22.5 fångar.

Redigerat 2 November 2012 av Dave37

[WASD]

Som jag sa, "Allt detta kom jag på genom att ha läst ord som "dimensioner" och "sida av kuben" som ni nämnt tidigare. Så det är kanske detta ni sagt."

 

Med valfri geometrisk form verkar man behöva mängden hörn i fångar och då kunna testa mängden hörn+kanter i flaskor.

 

-----

 

Jag tänkte vidare och hittade på det här som kan vidareutvecklas.

 

1 .2. .3. 4

5 ___ ___ 6

7 ___ ___ 8

9 10 11 12

 

12 flaskor. Och som innan har man totalt 4 personer med varsin kant. Men här lägger vi på en extra person som dricker till exempel, 2+5+6+10. Alltså en av de två i de fetmarkerade partierna. Om personen som hade den högra kanten dör kan man alltså med denna extraperson få reda på om det var 6 eller 8 som var förgiftat. 5 personer för att undersöka 12 flaskor. Detta kanske funkar bättre i högre dimensioner eller med mer än en extraperson. Eller att man lägger kanske 8 flaskor emellan hörnen och kör samma metod rekursivt. Det vill jag slippa tänka på! Rekursion inom programmering är jobbigt nog.

 

Fast jag har tänkt och räknat lite och den metoden verkar inte bli så bra.

Redigerat 2 November 2012 av WASD

[Dave37]

Nu är jag jävligt trött och har inga grunder för mitt resonemang, men trenden vi ser säger ju att ju större procent av antalet fångar man använder som dör desto färre fångar verkar man behöva ha. Jag menar, tänk om man bara behövde fem fångar för att visa vilken flaska som var förgiftad av alla de tusen ursprungliga fångarna. Det känns ju då rimligt att anta att nästan alla dör, antagligen 4 av fem, och att man från det kan få fram vilken flaska som är förgiftad. Kanske är det ett bra tillvägagångssätt att försöka maximera dödsrisken under testet istället för att fokusera på kuber och annat tjaffs? ;)

[Mezox]

Kommer nog kommentera mer senare men jag fortsätter lite på det Dave nämnde sist med att maximera dödsrisken.

 

Tänk på att om man har en metod som gör att 4 av 5 dör så får man en helt ekvivalent metod genom att alla istället smakar på de flaskorna som de inte smakade på i den urpsrungliga metoden (varenda fånge skiljer ju ff på samma flaskor bara att "överleva" och "dö" byter roll) och då hade man fått bara 1 av 5 död.

 

Ett mer matematiskt sätt att se detta är (och kanske ett tips för att hitta bästa talet?): Om vi har en uppställning där de flesta dör så har vi inte så många olika möjligheter som är sannolika. Om vi exempelvis har en uppställning med en stor chans att 4 av 5 provsmakare dör så kan vilka 4 provsmakare som dör endast väljas på 5 sätt. Med andra ord kommer majoriteten av fördelningen av giften att avbildas på endast dessa 5 fall, vilket gör det väldigt svårt att skilja på var giftet ligger.

 

Om däremot endast 2 eller 3 av 5 dör får vi 10 olika fall. Det är ju inte så mycket heller men det är definitivt mer än 5. Min poäng är att vi verkar få bäst resultat nära mitten, alltså när de flesta av fallen resulterar att ungefär hälften av fångarna dör. Det kanske därför är rimligt att anta att vi får bäst resultat ungefär då man har 50/50 chans att dö (med det inte sagt att alla sådanna test är bra).

 

WASD du upprepar det som mumutio redan har sagt, vi har redan löst problemet om man ställer upp flaskorna i en kub eller någon annan jämnsidig kropp vars vinklar mellan sidorna är 90 grader i valfri dimension mellan 1 och 10.

 

Med fyra dimensioner behöver man 22.5 fångar.

Vill bara säga att vi har kommit fram till att 10 är den bästa dimensionen för 1000 flaskor :D inte bara för 1 till 10 utan för alla dimensioner ^^

[WASD]

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

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?

[Dave37]

Det där är fan genialt.

[WASD]

Tack.

[Dave37]

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.

Redigerat 3 November 2012 av Dave37