View Single Post
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. 08:12.