Mezox

Bra :D

Kom igen! Haha en lättare (tror jag?) uppgift då (som är matematiskt mer avancerad): Bevisa att om 2^n + 1 är ett primtal och n är positivt så är n en tvåpotens. Och sist men inte minst, en som inte borde vara alltför svår om man gillar att räkna grejer (haha hittade på uppgiften nyss): En myra står i ett rutnät (den står i ett av "hörnen" i kvadraterna som bildas). Varje minut går myran slumpvis ett steg åt höger, vänster, upp eller ner. Vad är sannolikheten att myran efter åtta steg är tillbaks där den började? Om jag inte får lösningar fortsätter jag gå ner i svårighetsgrad.

"If one only wished to be happy, this could be easily accomplished; but we wish to be happier than other people, and this is always difficult, for we believe others to be happier than they are." Montesquieu

Där kom det :D

Studenterna skiljs från varandra. Om t.ex. två studenter från olika lägenheter byter plats så har vi en ny kombination. Jag vill påpeka att det kanske var en överdrift att mattekunskaper inte behövdes. Tekniskt sett behövs det inte men det hjälper att kunna några knep.

Väntar ff på att någon gör en "smart" kommentar om att det ÄR ett UFO så länge grejerna flyger.

Kom igen! Jag hade iaf förväntat mig att WASD hade skrivit ett program för att lösa det vid det här laget.

Det kan inte bo 4 pers i alla tre lägenheterna eftersom det bara finns 10 studenter :P men det KAN bo 4 pers i en lägenhet.

Livar upp tråden ännu en gång! Det finns tre studentlägenheter (tomma) där det kan bo maximalt 4 studenter i varje lägenhet. På hur många olika sätt kan 10 studenter flytta in i de tre lägenheterna? (Notering: De tre studentlägenheterna är olika. Det blir alltså ett annat fall om alla boende i en lägenhet byter plats med alla boende i en annan) Uppgiften kräver inte någon avancerad matte alls i princip utan man behöver bara kunna räkna rätt och hålla tungan rätt i mun.

Jag misstänker att det inte var det han menade :P

Jag gillar problemet eftersom det är lätt att förstå (de flesta som går gymnasiet bör kunna förstå vad problemet går ut på) men kan ändå leda till intressanta diskussioner. Tycker ni vi ska ha fler trådar med matteproblem? (eller kanske liva upp den gamla matteproblem-tråden?) :D

Hur resonerar du? Daves poäng är att precis som man kan avstå att köpa mat från ICA så kan man avstå från att jobba och betala skatt. Det betyder inte att du får mat.

Man kan ha 3273390607896141870013189696827599152216642046043064789483291368096133796404674554883270092325904157 150886684127560071009217256545885393053328527589376 fångar och låta de smaka på ett sådant sätt att man aldrig kommer kunna veta vilken flaska som är giftig (oavsett vilken den giftiga är)

Du gör det svårare än det behöver vara :P Du har 998 flaskor. Du KAN göra en fall-för-fall grej med 1 flaska upp till alla 998 flaskor. (jag antar här att det är tillåtet att en av fångara inte smakar på någon flaska alls) 0 flaska: Man kan smaka på 0 flaskor på 998 över 0 sätt. 1 flaska: Man kan smaka på 1 flaska på 998 över 1 sätt. 2 flaskor: Man kan smaka på 2 flaskor på 998 över 2 sätt. .... 998 flaskor: Man kan smaka på 998 flaskor på 998 över 998 sätt. och sen summera allt detta... Detta blir dock onödigt komplicerat, men om man gör det får man: http://www.wolframalpha.com/input/?i=Sum+%...k+from+0+to+998 Det andra sättet att räkna på det är att man tänker att man för varje flaska kan låta en given fånge antingen smaka på den, eller inte smaka på den. Antalet möjliga urval som finns (och varje urval svarar mot en fånge) blir då 2^998. Och detta "råkar" bli samma som det i länken. (som ni kanske förstår är detta inget sammanträffande utan det är en konsekvens av binomialsatsen ). Notera nu detta: För varje fånge A kan vi nu lägga till en fånge B som smakar på de flaskor A smakar på OCH de två extra vi tog bort. Eftersom han smakar på båda kommer man fortfarande inte kunna skilja dem åt. Detta tar det totala antalet fångar till 2^999 = 5357543035931336604742125245300009052807024058527668037218751941851755255624680612465991894078479290 63797336458776573412593572642846157021799228878734928740196728388741211549271053730253118557093897709 1076523237491790970633699383779582771973038531457285598238843271083830214915826312193418602834034688

Dave: Ahh förstår vad du menar med "ta bort". Du kanske kan prova att ta bort två flaskor, varav ena är giftet?

Jag förstår inte. Hur tar man bort det förgiftade vinet om man inte vet vilken den är?

Förklara gärna hur :D

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

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

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.

Flest som behövs :P

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

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

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?

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