Hur Räddar Vi Kejsarens Fest?

[Mezox]

Det fanns en gång en kejsare som skulle ha en fest om ett dygn. Han hade förberett 1000 flaskor vin att servera på festen men olyckligt som det är får han information om att exakt en av flaskorna är förgiftad. Giftet ändrar inte några egenskaper på vinet (typ vikt, lukt, smak) som kejsaren med sin teknologi kan mäta direkt (detta hände för längesen). Det enda han vet är att den som dricker av den förgiftade flaskan dör om exakt ett dygn utan föregående symptom.

 

Kejsarens lösning är att låta 1000 fångar smaka på en flaska var och när en av dem dör efter ett dygn tar han bort motsvarande flaska från festen. Som man kan gissa är det inte så effektivt med 1000 fångar då det tar mycket arbete att ha koll på alla medan de smakar osv.

 

Kan ni hitta lösningar som kräver färre fångar som provsmakare?

 

För dem av er som är extra oscillativa kan ni generalisera till n flaskor!

Redigerat 1 November 2012 av Mezox

[Dave37]

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.

[Mumutio]

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

Redigerat 1 November 2012 av Mumutio

[Mezox]

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.

[Dave37]

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.

Redigerat 2 November 2012 av Dave37

[Mezox]

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.

[Dave37]

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.

[WASD]

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.

Redigerat 2 November 2012 av WASD

[Mezox]

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.

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

 

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?

[Dave37]

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.

[Mezox]

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

[Dave37]

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