Hur Räddar Vi Kejsarens Fest?

Jag orkar inte räkna på det exakt man man gör ju något i stil med att flera fångar smakar på flera flaskor, men olika kombinationer av dem så att sen när ett gäng fångar dör så kan man se vilken flaska de har gemensamt och så är det konstruerat så att de måste ha en och endast en flaska gemensamt vilken är den förgiftade.

Sen om man tycker det är mer "effektivt" att låta flera fångar dö och låta mer vin gå åt för "testning" är en annan fråga.

Precis. Eftersom att det är exakt 1000 flaskor blir det enkelt att räkna. Det kan ju vara lämpligt att föreställa sig flaskorna uppställda i en kub, där 10 fångar får provsmaka varje sida av kuben, och de får provsmaka en "skiva" var. Då får varje fånge provsmaka 10*10=100 flaskor var och det behövs endast 30 fångar.

När en fånge dör vet man att det var bland någon av de där 100 flaskorna som den förgiftade fanns, så kan man avgränsa vilken rad det var i den "skivan" av flaskor genom att se vilken fånge som dog på nästa sida av kuben, och sedan hitta vilken flaskan av de 10 i raden som är förgiftad genom att se vilken av fångarna på den sista sidan som dog.

Så för n flaskor är det väl helt enkelt tredjeroten ur antalet flaskor n man får använda som sida på den imaginära kuben, sen multiplicera med tre för att få antalet fångar man behöver. :P

Finns säkert fler metoder. Kanske kan använda fjärderot också osv? Jag är dock inte så duktig på abstrakt matte, tycker om att konkretisera som ni kanske märker.

Men för varje gång man tar roten en extra gång krävs det väl antagligen fler provsmakningar och fler döda fångar. Om jag får chansa blir det m*n provsmakningar om m är antalet gånger man tar roten ur antalet flaskor n, samt m fångar som dör. Antalet fångar som behövs blir (m:e roten ur n)*m.

Skippar bevisningen haha, tycker det är så jobbigt. ;)

Så ursäkta det halvmatematiska språket. Kul problem. :)

Kreativ lösning Mumutio, snyggt! 30 fångar är definitivt färre än 1000 :D . Absolut lugnt att det inte är "matematiskt". Jag har sett för många försök där någon försöker göra ett simpelt argument för matematiskt och df komplicerar till det!

Finns det någon som kan slå 30 fångar?

Dave: Jo, det är det som är tanken, men det "svåra" är att komma på hur man gör det så bra som möjligt, och juste man bryr sig inte om fler fångar dör (rättssäkerheten är inte så bra hehehe), utan bara att man inte ska använda så många.

Sådana här problem roar mig bara att räkna ut faktiska lösningar till om det är till någon "nytta". ;)

Om inte så tycker jag att principen bakom lösningen är det viktiga.

Haha okej då ditt val. Själv tycker jag det e kul att försöka hitta det bästa sättet att göra det på.

Hur lågt kan vi komma? :D

Förresten, om det finns andra som hittar metoder att göra det på mindre än 1000 kan ni gärna berätta det även om det inte når ner till Mumutios 30. Det jag gillar med problemet är att det funkar för många olika nivåer.

bortsett att flaskorna och fångarna är naturliga och inte går att dela i delar av sig själva så borde en "effektiv lösning" vara att ställa upp en "kub" i ln(1000)-dimensionen. Om man för samma resonemang som Mumutio så låter man varje fånge smaka en "skiva" i dimensionen under, alltså varje fånge smakar på 1000/e flaskor. Då behöver e*ln(1000) fångar vilket är ungefär 18.777 st.

I problemet för n flaskor så gäller det att se till att roten (vilken rot man nu tar) av n är ett heltal, annars för det matematisk optimerade svaret gäller att ln(n) är den dimensionen "kuben" bör ha som ger minst antal fångar. Förutsatt att jag räknat rätt tänkte inte så jättenoga.

Jag har inte läst igenom men detta kan vara som binärsökning inom programmering. Vi har två fångar som smakar på 500 var. Och när en dör, så delar vi upp dens 500 till två nya fångar som får 250 var. Inom programmeringen kan man använda något med logaritmer för att få fram hur många steg det kommer bli vilket kanske är det Dave pratar om.

Men om man tar 500, 250, 125... så behövs totalt 10 steg för att komma ner till 1. Då borde det alltså ta 10 dagar att få fram vilket flaska det var. Om man har färre dagar på sig kan man kanske dela upp det i 4 delar istället för 2 och det skulle ta 5 dagar att få fram. Och en fånge dör ju varje dag.

Edit: Jaha. Festen skulle vara imorgon. Då håller inte det jag skrivit. Annars skulle det vara ett bra sätt att balansera hur många fångar man vill låta dö och hur många dagar man har på sig.

↗ till inlägget

Jag har inte läst igenom men detta kan vara som binärsökning inom programmering. Vi har två fångar som smakar på 500 var. Och när en dör, så delar vi upp dens 500 till två nya fångar som får 250 var. Inom programmeringen kan man använda något med logaritmer för att få fram hur många steg det kommer bli vilket kanske är det Dave pratar om.

 

Men om man tar 500, 250, 125... så behövs totalt 10 steg för att komma ner till 1. Då borde det alltså ta 10 dagar att få fram vilket flaska det var. Om man har färre dagar på sig kan man kanske dela upp det i 4 delar istället för 2 och det skulle ta 5 dagar att få fram. Och en fånge dör ju varje dag.

 

Edit: Jaha. Festen skulle vara imorgon. Då håller inte det jag skrivit. Annars skulle det vara ett bra sätt att balansera hur många fångar man vill låta dö och hur många dagar man har på sig.

Dave: Jag tycker det är en väldigt intressant tanke (jag antar att du fick den genom att minimera funktionen f(x) = x*1000^(1/x), där x är dimensionen) men jag undrar hur lätt det är att översätta lösningen till ett prakiskt tillvägagångssätt, eftersom irrationella (och kanske i synnerhet transcendenta) dimensionstal är väldigt svåra att visualisera (jag vet att det finns fraktaler med icke-heltalsdimensioner t.ex.).

Det jag kan tänka mig är att man använder det närmsta heltalet, alltså kub i dimension 7. För att kunna innehålla alla flaskor måste man ha en sidlängd på 3 (eftersom 1000^(1/7) ungefär blir 2,68) och då får man 7*3 = 21 fångar. Det jag märker är dock att 2,68 är en ineffektiv sidlängd eftersom vi får så mycket plats över (0,32 på varje sida). Med lite prövning ser vi att 1000^(1/x) hamnar precis under 2 då x=10 (1000^(1/10) är ungefär 1,995) och man får då 2*10 = 20 fångar.

Med andra ord: Om man ordnar vinflaskorna i en tiodimensionell "kub" behöver man bara 20 fångar, vilket är det optimala antalet man kommer kunna få med en sådan kubindelning. :P

Frågan återstår om annan typ av indelning kan vara mer effektiv?

genom att maximera funktionen g(x) = 1000^(1/x)-floor[1000^(1/x)] kan man hitta de dimensionstal som är närmast heltal om man vill hitta lösningar skilt från 3 och bättre än x = 10. Vet inte om de finns dock. Jag testade med 10 först men sen tänkte jag att vad fan ska vi hålla på med ickeexakta sidlängder (om än nära heltal) så kan vi lika gärna optimera skiten.

@WASD: nä jag använder samma resonemang som mumutio jag bara expanderar det till ett rent matematiska problem.

Inget större än 10 kan vara bättre än 10 eftersom alla kuberna måste ha sidlängd 2 (om den är 1 får bara en vinflaska plats). Och ju större dimension desto mer "döplats" finns det. De som är mindre än 10 kan man testa för hand (varav jag inte tror någon kan bli bättre än 20 fångar).

Det är lite intressant vad som händer med sannolikheten att dö om man är fånge i de olika scenariorna. I kungens fall är det 0.1% risk att dö, i mumutios fall är det 10% risk, i mitt fall 1/e (ca 36.8%) risk och i Mezoxs fall ca 50%.

↗ till inlägget

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

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

↗ till inlägget

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

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!

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.

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.

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? ;)

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

↗ till inlägget

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.