Du må være registrert og logget inn for å kunne legge ut innlegg på freak.no
X
LOGG INN
... eller du kan registrere deg nå
Dette nettstedet er avhengig av annonseinntekter for å holde driften og videre utvikling igang. Vi liker ikke reklame heller, men alternativene er ikke mange. Vær snill å vurder å slå av annonseblokkering, eller å abonnere på en reklamefri utgave av nettstedet.
  25 3037
En smule inspirert av slashdot sin tråd om kreative fremgangsmåter for Hello World kommer det en utfordring av et helt annet kaliber. Jeg har ikke skrevet denne selv og det er fullt mulig å finne svar på det matematiske problemet om man har litt google-skills (det får dog være en oppgave for hver enkelt). Jeg vil også oppfordre folk til å diskutere løsningsforslag for å hjelpe hverandre.

Oppgaven er som følger:
Hundre fanger (nummerert 1 til 100) er dømt til døden, men får en sjanse til
benådning. En etter en sendes de inn i et rom, der det er hundre like bokser
(også nummerert 1 til 100). I hver av boksene ligger det en lapp med et tall
fra 1 til 100 på (inklusive, hvert tall brukes en gang). Lappene er helt
tilfeldig fordelt ut mellom boksene.

Hver fange kan bruke så lang tid han/hun vil der inne, men ikke åpne mer enn
femti bokser. Målet er å finne «sin egen» lapp, altså lappen som har samme
nummer som sitt eget fangenummer, på maksimalt femti forsøk (åpning av
bokser, altså). Hvis _alle_ hundre klarer dette, benådes de, mens hvis så mye
som én feiler, skytes hele bunten. (Fangevokterne er alltid ganske diabolske
i sånne oppgaver...)

Nå til det som gjør oppgaven vanskelig: Så fort førstemann har gått inn i
rommet, er det absolutt ingen kommunikasjon, hverken implisitt eller
eksplisitt, mellom noen av fangene. Med andre ord, så fort man har funnet sin
lapp går man ut av rommet og snakker ikke med noen av de andre, og rommet
settes tilbake til den tilstanden det var i (alle bokser lukkes igjen, evt.
lapper som er tatt ut legges tilbake igjen, evt. skribling på veggen vaskes
bort, osv.). Du kan med andre ord ikke bruke ting som «første fange var der
i 14 minutter om han fant lappen sin i boks nummer 14» eller tilsvarende.
Vis hele sitatet...
Oppgaven er altså todelt:

1. Finn en strategi som gjør at det er minst 30% sannsynlighet for
at de blir benådet. (Optimal strategi gir litt over 31% eller så; det er
matematisk veldig utfordrende å faktisk regne ut sannsynligheten, så det er
ikke en del av oppgaven. Det holder å gi riktig strategi, så kan man alltids
simulere den for å vise at det faktisk blir over 30% etterpå.)

2. Implementer denne i selvvalgt programmeringsspråk.

(ps: Dette er ikke et "lurespørsmål", ordlyden i oppgaven har ingen betydning, fangene kan ikke rotte seg sammen for å overmanne vaktene etc. Det er beint frem et problem med en løsning som er vanskelig å finne.)

Jeg gir dere en uke til å tenke over/diskutere problemstillingen før jeg poster en forklaring til hjelp i implementeringen.
Queen of Blades
Jonta's Avatar
DonorCrew
Jeg antar at en ikke kan si "Jamen denne boksen var tom, da telles det ikke!"?

Edit: Vent, de tar altså ikke lappen ut av boksen, og går ut av rommet med den?
Sist endret av Jonta; 17. februar 2009 kl. 14:04.
Du sier at de ikke kan kommunisere ETTER at førstemann har gått inn. Dvs at de kan planlegge utførelsen på forhånd?
Logotytme
liasis's Avatar
Trådstarter
Jonta: Nei, når en gitt fange har klart sin del av oppgaven går han ut av "oppgaverommet" og alle lapper og bokser resettes. Fangene har ingen kommunikasjon seg i mellom, man kan anta at de f.eks sitter på hver sin celle.

zairox: Ja
Sist endret av liasis; 17. februar 2009 kl. 14:27.
Queen of Blades
Jonta's Avatar
DonorCrew
Da tråden er åpen for diskusjon, så blir sannsynligheten for at alle finner den sånn uten videre 50% * 50% * 50% osv. Altså (1/2)^100 = 7,9 * 10^-31. Dette er altså ikke en plausibel løsning.

Åpent spørsmål: Kan en fange øke sannsynligheten for at han/hun finner sin egen boks til mer enn 50%?
Kan fangene avtale å prøve denne og denne boksen? I en rekkefølge kanskje?

moridin: Vet de hvordan boksene er satt opp/plassert? Er de på rekke elns?

Nei vent, de er jo nummerert, så de kan planlegge at første fange prøver fra 1-50, 2. fra 2-51 osv. Right? Kan det hjelpe?
Logotytme
liasis's Avatar
Trådstarter
Jonta: Nei, det vil ikke hjelpe. Om fange #1 skal ta 1-50 og ikke finner sitt eget nummer vil hele oppgaven feile. Dermed får du fortsatt bare 50/50 om man lykkes eller ikke pr fange, rimelig dårlige odds altså.

Men det er på tide med et lite hint: At fangene er nummererte i denne versjonen gjør den bittelitt lettere enn originalen hvor de kun er navngitte.
Er det ikke noe med at lyset kan skrus av og på?
Asosial sosialist
Cheroxx's Avatar
Haha tror nok du blander ganske drøyt mellom forskjellig oppgaver her.
Trikset er at de må stikke hodene sammen på forhånd, og gi hver av boksene ett tall, Nermest til høyre er 1, lengst til venstre er 100, om man forstår.
Etter at de har gjort dette går fangen inn i rommet, og begynner med boksen som har fått sitt nummer angitt, om han ikke finner sitt eget nummer i den boksen fortsetter fangen og se i den boksen som hadde fått tillegnet det nummeret fangen fant i den første boksen, dette fortsetter til fangen har funnet sitt navn, eller åpnet 50 bokser.

Om alle fangene gjør dette ender de opp med en 31% ish sjangse for og overleve.

Jeg har fått den forklart for en godr stund siden, og husker fint lite om hvorfor det fungerer slik, og ikke kan jeg noen programeringsspråk.
Har fangene lov til å bytte rundt på lappene som ligger i boksene, eller går det under kommunikasjon?
Sitat av The Freak Vis innlegg
Har fangene lov til å bytte rundt på lappene som ligger i boksene, eller går det under kommunikasjon?
Vis hele sitatet...
Han skrev vel at alt resettes etter hver fange som har vært inne. Så om en fange bytter rundt på lappene vil vel disse legges tilbake etter fangen har gått ut
Sitat av mordin
...(alle bokser lukkes igjen, evt.
lapper som er tatt ut legges tilbake igjen, evt. skribling på veggen vaskes
bort, osv.)...
Vis hele sitatet...
Dette betyr at fangene har noe å skrive med?
Kan da første fange åpne boks 1-50 og andre fange åpne 51-100. Og da skrive ned på lappen i boks nr 1 og 2 hvilke nr som er i de andre boksene? Siden boksene er nummerert blir det noe slik:

Kode

Boks:   Nr:
1   =   72
2   =   37
3   =   24
4   =   68
5   =   83
etc.
Da har første og andre fange 1/50 sjangse for å finne deres egen lapp, mens alle de andre fangene finner sin lapp ved å åpne boks 1 eller 2.
Måten som hardcore nevner er vel den som stemmer.
Men jeg er ikke noen kløpper i programmering jeg heller.
Før jeg la meg programmerte jeg dette i C++. Setter opp enn array (boksene) og går gjennom den på hardcore sin måte.

http://pastebin.com/m5297ffcd

Har lagt merke til 2 ting:
1. Vanligvis, HVIS de feiler, så er ca. alltid de første (vanligvis nr. 1 eller 2).
2. De treffer vanligvis på forsøk 49 eller 50. ^^

Mulig jeg har gjort/sagt noe feil, er for trøtt til å spinne i gang hjernen.

Glem nr. 2, ser ut som om den ikke stemmer likevel ... :/

Fails: 68807
Wins: 31193
% Win: 31%
Sist endret av boblehest; 18. februar 2009 kl. 01:25. Grunn: Automatisk sammenslåing med etterfølgende innlegg.
Queen of Blades
Jonta's Avatar
DonorCrew
Sitat av Clr Vis innlegg
Dette betyr at fangene har noe å skrive med?
Kan da første fange åpne boks 1-50 og andre fange åpne 51-100. Og da skrive ned på lappen i boks nr 1 og 2 hvilke nr som er i de andre boksene? Siden boksene er nummerert blir det noe slik:

Kode

Boks:   Nr:
1   =   72
2   =   37
3   =   24
4   =   68
5   =   83
etc.
Da har første og andre fange 1/50 sjangse for å finne deres egen lapp, mens alle de andre fangene finner sin lapp ved å åpne boks 1 eller 2.
Vis hele sitatet...
Nei, det går ikke. Hvordan kommer du da forresten fram til 31%? Alt resettes.

Eh, jeg tror jeg forstår framgangsmåten til Hardcore, men hvorfor virker den?

Jeg forstod den slik: Fange 92 går inn, åpner boks 92. Finner lapp 35. Går til boks 35. Finner lapp 84. Går til boks 84. Osv. Right?
Python-implementasjon: http://pastebin.com/m6202484f

Kode

100000 runs, 33178 wins, 66822 losses - 0.331780 rate
Strategien er enkel, men vanskelig å forklare. Fangene behandler skapene som lenkede lister, hvor det første skapet de sjekker (Skap #1) er det med samme nummer som fangenummeret. Hvis de åpner feil skap så er neste gjetning det skapet som lappen i Skap #1 tilsier. Slik går det da til de enten går tom for forsøk eller finner riktig.

'Trikset' her er at de utnytter det at første person kom seg videre, ikke opptrer som enkelthendelser. Den første personen som går inn har 50% sannsynlighet for å klare seg, men GITT AT fange #1 faktisk kommer seg ut så kan nestemann gå inn og starte på en ny plass i den lenkede listen (som ikke nødvendigvis trenger å være en sirkel, det kan hende at skap 1 inneholder lapp 2 og skap 2 inneholder lapp 1).
Etter litt tenking har jeg også forstått dette.
Som Dyret sier, så fungerer dette som lenkede lister, og det kan være flere lenkede lister.
Etter litt tenking skjønte jeg at selvfølgelig når en begynner på f.eks. boks 37, så vil den siste boksen i denne lenkede listen være den som peker tilbake til boks 37, så de vil bare klare det om ingen av disse tenkte listene overskrider enn lengde på 50 (antall forsøk).

Den matematiske formelen for å regne ut sjansen skal jeg la noen andre ta seg av.
Sist endret av boblehest; 18. februar 2009 kl. 02:14.
For de interesserte finnes sannsynlighetsregning her: http://www.mast.queensu.ca/~peter/in.../prisoners.pdf
Logotytme
liasis's Avatar
Trådstarter
Kudos til Hardcore for å komme med riktig løsning, selv om du hadde fått den forklart og ikke skjønner hvorfor

Uansett, siden Dyret har implementert den allerede ser jeg ingen grunn til å drøye særlig mer og poster derfor Sesse's rimelig enkle forklaring på hvordan det fungerer (også litt sånn at slashdot slipper å kaste bort flere arbeidsdager på å gruble over problemet):

Første innsikt er at man er nødt til å bruke nummeret man får i boksen på noe
vis, ikke bare «var det rett tall?» (ja/nei). Det mest nærliggende da er å
rett og slett gå til den tilhørende boksen -- altså, trekker du nummer 15 går
du til boks nummer 15 og ser der.

Før eller siden vil du da havne tilbake der du startet, altså, du går i ring.
Si for eksempel at du har fem bokser som har følgende lapper i seg:

Boksnummer 1 2 3 4 5
Lapp 3 5 1 2 4

Her har vi altså løkkene 1-3-1 og 5-4-2-5. Enhver permutasjon av lapper vil
bestå av slike løkker som ikke overlapper (hvis du vil si det litt fint kan
du kalle det "produkt av disjunkte sykler"). Altså er målet å komme seg inn
på løkken som inneholder din egen boks, og så følge den til du kommer rett
sted.

Akkurat dette har en fryktelig enkel løsning: Du bare starter på boksen som
har samme nummer som deg selv. Så om du er nummer 1, går du til boks nummer
1, ettersom du vet at siden det er en løkke, må det finnes en lapp i kjeden
som peker tilbake til boks nummer 1 (som er den lappen du vil ha).

Så, i hvilke tilfeller går dette bra, og hvilke går det dårlig? Det er ikke
fryktelig vanskelig å se at om du har en løkke som er over lengde 50, vil det
gå dårlig for alle som er på den løkken -- ettersom du begynner på verst
tenkelige sted i løkken, må du følge hele før du kommer til slutten. (Du får
med andre ord enorm korrelasjon mellom hver fange, som vi jo har sagt vi
ville ha.) Det viser seg imidlertid at det skal litt til før du får en så
lang løkke i en tilfeldig permutasjon; dersom det hele tiden er tilfeldig
hvilken lapp du trekker, er det ganske så sannsynlig at du etter hvert vil
trekke en lapp som hører til en boks der du har vært før, og da er løkken
sluttet.

Det går an å regne på det, men det er litt utenfor det jeg orker å skrive ned
akkurat nå -- men sannsynligheten for at lengste sykel i en slik tilfeldig
mapping er under 50 elementer lang, er ca. 31.1%, som er det vi skulle fram
til.
Vis hele sitatet...
Originalen finnes her: http://www.math.princeton.edu/~wwong...08191813.shtml
Sist endret av liasis; 18. februar 2009 kl. 09:12.
Hvorfor gir dette programmet 29,9% sjanse: (1 million tester, samme hver gang)

import java.util.*;

public class Fanger{


public static final int NR_CHANCES = 50;
public static final int NR_BOXES = 100;
public static final int NR_PRISONERS = 100;
public static int[] boxes = new int[NR_BOXES];


public static void main(String[] args){

//Initialiserer boxes,
randomizeboxes();


int successes = 0;
int nr_tests = 1000000;
for (int i = 0; i < nr_tests; i++){
if (allsurvives())
successes++;
randomizeboxes();
}

System.out.println("Overlevelsessjanse: " + (1.0*successes/nr_tests) );

}




//Returnerer true om alle fanger klarer det.
public static boolean allsurvives(){
for (int x = 0; x < NR_PRISONERS; x++){
if (!successfullcoice(x, x))//merkelig kall, ser det, men lettere se hva som gjøres
return false;
}
return true;
}


//returnerer true om én fange klarer det.
public static boolean successfullcoice(int startbox, int prisonnumber){
int choicesmade = 0;

while (choicesmade < NR_CHANCES){
int choice = select(startbox);
if (choice == prisonnumber)
return true;

choicesmade++;
startbox = choice;
}
return false;
}



public static int select(int boxnumber){
return boxes[boxnumber];
}


//Trekker tilfeldig lapp til hver box.
public static void randomizeboxes(){
for (int x = 0; x < NR_BOXES; x++){
boxes[x] = x;
}
//shuffle the array:
Random r = new Random();
for (int i = 0; i < boxes.length; i++) {
int newposition = r.nextInt(boxes.length);
int temp = boxes[newposition];
boxes[newposition] = boxes[i];
boxes[i] = temp;
}
}

}
Vis hele sitatet...
Sitat av Swiss79 Vis innlegg
Hvorfor gir dette programmet 29,9% sjanse: (1 million tester, samme hver gang)
Vis hele sitatet...
hvis du flytter initialiseringen av boxene ut til en egen metode så fungerer programmet ditt riktig: "Overlevelsessjanse: 0.311233"

oppdatert kode:

Kode

import java.util.*;

public class Fanger{

public static final int NR_CHANCES = 50;
public static final int NR_BOXES = 100;
public static final int NR_PRISONERS = 100;
public static int[] boxes = new int[NR_BOXES];

public static void main(String[] args){

//NEW: initializes boxes
initializeBoxes();
//randomizes boxes
randomizeboxes();


int successes = 0;
int nr_tests = 1000000;
for (int i = 0; i < nr_tests; i++){
if (allsurvives())
successes++;
randomizeboxes();
}

System.out.println("Overlevelsessjanse: " + (1.0*successes/nr_tests) );

}

//Returnerer true om alle fanger klarer det.
public static boolean allsurvives(){
for (int x = 0; x < NR_PRISONERS; x++){
if (!successfullcoice(x, x))//merkelig kall, ser det, men lettere se hva som gjøres
return false;
}
return true;
}


//returnerer true om én fange klarer det.
public static boolean successfullcoice(int startbox, int prisonnumber){
int choicesmade = 0;

while (choicesmade < NR_CHANCES){
int choice = select(startbox);
if (choice == prisonnumber)
return true;

choicesmade++;
startbox = choice;
}
return false;
}

public static int select(int boxnumber){
return boxes[boxnumber];
}

//Trekker tilfeldig lapp til hver box.
public static void randomizeboxes(){

//shuffle the array:
Random r = new Random();
for (int i = 0; i < boxes.length; i++) {
int newposition = r.nextInt(boxes.length);
int temp = boxes[newposition];
boxes[newposition] = boxes[i];
boxes[i] = temp;
}
}

public static void initializeBoxes(){
	
	for (int x = 0; x < NR_BOXES; x++){
		boxes[x] = x;
		}
}

}
Ja visst... Eneste forskjellen er at i opprinnelig program shufflet jeg alltid fra utgangsposisjon, og i ny versjon shuffler jeg fra rekkefølgen siden sist shuffle. Om jeg f.eks. kaller initializeBoxes() i starten på getrandomizedboxed(), så dukker den gamle feilen opp igjen.

Er det et utslag av at Random bare er pseudorandoms? Forsøkte med en løsning hvor jeg garanterte ulike seeds for hver gang, fungerte ikke. Heller ikke å kun lage objektet Random r én gang (som jo er greiere uansett, da er du nå i hvertfall sikker på at ikke samme seed benyttes) fungerte.

Mem om jeg endrer array shufflingen til :
//shuffle the array:
int numberShuffles = 500;
for (int i = 0; i < numberShuffles; i++) {
int newposition = r.nextInt(boxes.length);
int temp = boxes[newposition];
int boxToBeSwitched = r.nextInt(boxes.length);
boxes[newposition] = boxes[boxToBeSwitched];
boxes[boxToBeSwitched] = temp;
}

...så fungerer gamle løsningen også. (tar riktig nok laang tid da, var bare for å sjekkke)

Med numberShuffles lavere funker det ikke så bra..100 ganger gir feks 0.526


Takk for løsningen! Men vil gjerne vite hvorfor ...har en følelse av at jeg overser noe opplagt da...men kanskje ikke.
Jeg synes blanding er en dårlig måte å gjøre det på.
Dette er metoden jeg pleier å bruke, noen som vet om noen bedre måte?

Kode

int box[100]; //Boksene
bool used[100]; //Liste over hvilke tall som er brukte

//Sett alle 'used' verdiene til false
long * p = (long *)used;
while ((bool*)p < &used[100])
    *p++ = 0;

int num;
for (int i = 0; i < 100; ++i)
{
        num = rand() % (100-i); 
        for (int j = 0; j <= num; ++j) //Hvis tallet ble f.eks. 17, så velger den tall nr. 17 (eller 18 siden man teller fra 0) blant de ledige tallene
                if (used[j]) //Hvis 2, 5 og 18 er brukte, så vil det nye tallet bli 20
                        ++num;
        box[i] = num;
        used[num] = true;
}
Sist endret av boblehest; 6. mars 2009 kl. 18:07.
Sitat av Clr Vis innlegg
Dette betyr at fangene har noe å skrive med?
Kan da første fange åpne boks 1-50 og andre fange åpne 51-100. Og da skrive ned på lappen i boks nr 1 og 2 hvilke nr som er i de andre boksene? Siden boksene er nummerert blir det noe slik:

Kode

Boks:   Nr:
1   =   72
2   =   37
3   =   24
4   =   68
5   =   83
etc.
Da har første og andre fange 1/50 sjangse for å finne deres egen lapp, mens alle de andre fangene finner sin lapp ved å åpne boks 1 eller 2.
Vis hele sitatet...
Hvis fange nr 1 går inn og skriver ned nr på boksan 1-51 på lappen i boks 1, så har han ca 50% sjangs for å treffe på sin lapp... Så går nr 2 inn og skriver ned nr på boksan 52-100 på lappen i boks 2, og åpner boks nr 1, så har han 100% sjangs for å treffe på sin...
Og fangene 3-100 har også 100% sjangs å treffe på sin...
Så 99 fanger har 100% sjangs og 1 fange har 50% sjangs... 99*100+50/100 = 99% sjangs?

Eller tar æ feil?
Sitat av Masi Vis innlegg
Hvis fange nr 1 går inn og skriver ned nr på boksan 1-51 på lappen i boks 1, så har han ca 50% sjangs for å treffe på sin lapp... Så går nr 2 inn og skriver ned nr på boksan 52-100 på lappen i boks 2, og åpner boks nr 1, så har han 100% sjangs for å treffe på sin...
Og fangene 3-100 har også 100% sjangs å treffe på sin...
Så 99 fanger har 100% sjangs og 1 fange har 50% sjangs... 99*100+50/100 = 99% sjangs?

Eller tar æ feil?
Vis hele sitatet...
Herregud! Les oppgaven igjen.
Eller tar æ feil?
Vis hele sitatet...
Som sagt, les oppgaven på nytt. Spesielt denne delen:

Nå til det som gjør oppgaven vanskelig: Så fort førstemann har gått inn i rommet, er det absolutt ingen kommunikasjon, hverken implisitt eller
eksplisitt, mellom noen av fangene. Med andre ord, så fort man har funnet sin
lapp går man ut av rommet og snakker ikke med noen av de andre, og rommet
settes tilbake til den tilstanden det var i (alle bokser lukkes igjen, evt.
lapper som er tatt ut legges tilbake igjen, evt. skribling på veggen vaskes
bort, osv.
). Du kan med andre ord ikke bruke ting som «første fange var der
i 14 minutter om han fant lappen sin i boks nummer 14» eller tilsvarende.
Vis hele sitatet...
Fangene kan på ingen måte kommunisere med hverandre. Å skrive ned informasjon på lappene er da i høyeste grad kommunikasjon.