Tænkeboks: Ugens løsning

I sidste uges opgave skulle 100 fanger lægge en strategi for at forudsige, hvornår de alle, enkeltvis og tilfældigt udtrukket, havde været inde i en forhørscelle og vendt enten en 10krone eller en 20krone, hvis de på forhånd vidste, at begge mønter startede med at vise plat – eller hvis de ikke vidste, hvordan mønterne lå ved starten. Her er løsningen fra SDU, Mads Clausen Instituttet i Sønderborg:

Løsning på opgave 3:

Der er løsninger for begge tilfælde. Lad os starte med at begge mønter viser plat til at starte med.

Det fangerne skal gøre er, at beslutte sig for en fange, der tæller (lad os kalde ham ‘tælleren’), som også er den eneste, der må påstå at alle fangerne har været i cellen. Så er den grundlæggende strategi at alle fangerne bare vender rundt på 10kronen(dummy-mønten) uanset, hvad den viser, med følgende undtagelser, hvor 20kronen (tælle-mønten) bliver brugt:

Hvis 20kronen viser plat, skal de normale fanger vende den, så den viser krone. Det må hver fange kun gøre én gang. Herefter skal vedkommende altid vende 10kronen.

Hvis 20kr mønten viser krone, så skal tælleren vende den til plat og tælle en op.

Når tælleren har talt op til 99, så kan han være sikker på at alle fanger har været i afhøringscellen og kan påstå tilsvarende.

Man kan faktisk estimere det gennemsnitlige antal udvælgelser til at være omkring 10.000 før tælleren har talt til 99 – det tager gennemsnitligt 99 omgange før tælleren kommer ind i cellen igen, og han skal tælle til 99, så det tager 99^2 = 9.801 ture til forhørscellen (ikke medregnet de gange hvor 20kronen allerede viser plat, når tælleren kommer ind).

Tilfældet, hvor fangerne ikke kender starttilstanden, kan løses ved at modificere ovenstående. Problemet er at der er risiko for at tælleren bliver ført ind som første og 20kr mønten viser krone, i hvilket tilfælde han vil tælle – uberettiget.

Men det kan løses ved at hver fange vender 20kr mønten to gange og tælleren tæller til 199 i stedet for 99. Ved at tælle til 199 er tælleren sikker på, at 99 af fangerne har været til forhørscellen mindst to gange, og at den sidste har været det mindst én gang (hvis mønten viste plat til at starte med, har alle fangerne været inde 2 gange). Det kommer gennemsnitlig til at tage 20.000 ture til forhørscellen – dobbelt så mange som hvis de kendte starttilstanden!

– – –

Vi bringer en ny opgave i næste uge.

/Lynch

Illustration: MI Grafik
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først

Det er alligevel en skudsikker strategi. Jeg overså den med at de kun må vende 20'eren een gang. Til gengæld kan forsøget vare så længe at nogle dør undervejs.

  • 1
  • 0

Nu siges der i opgaven "helt tilfældig rækkefølge", men som opgaven åbenbart menes, skulle der have stået tilfældigt udvalgt eller andet lignende. Rækkefølge burde ikke have optrådt i teksten, da det faktisk har en væsentlig betydning, uanset om det er tilfældigt først. Måske jeg er en ordkløver, men i min optik har rækkefølge en bestemt betydning, som man ikke bare kan skøjte henover. I løsningen blev det til: hvornår de alle, enkeltvis og tilfældigt udtrukket, havde været inde i en forhørscelle, og det er noget helt andet og slet ikke hvad der stod i opgaven først.

Et sidespor: Er det sådan noget der gør at IT projekter løber af sporet?

  • 1
  • 1

Den løste opgave: De komplicerede løsninger er gældende, hvis fængselsinspektøren blot en gang imellem fører en tilfældig fange til forhør.

Den stillede opgave er noget simplere:

1: Tilfældig rækkefølge er ikke det samme som tilfældig udtagelse med tilbagelægning. Når fangerne tages i tilfældig rækkefølge, som teksen siger, behøves ingen strategi. Efter præcis100 dage har alle fangerne været til forhør.

2: Løsningen, at tælle til 199 forudsætter, at første fange ikke ved at han er første fange. Når der føres en tilfældig fange til forhør HVER dag, betyder ukendt starttilstand kun 1 ekstra dags fangenskab. På dag 1 skal skal fangen, tæller eller ej, blot efterlade 20-eren som plat.

  • 1
  • 0

1: Tilfældig rækkefølge er ikke det samme som tilfældig udtagelse med tilbagelægning. Når fangerne tages i tilfældig rækkefølge, som teksen siger, behøves ingen strategi. Efter præcis100 dage har alle fangerne været til forhør.

Rart at en anden også kan læse og forstå. Jeg var bange for at jeg var den eneste som opfattede rækkefølge på den måde, uanset hvor tilfældig den nu kan være. Det kan jo være det har en anden betydning i Sønderjylland, men det må Mads Clausen Instituttet så redegøre for.

  • 1
  • 0
Bidrag med din viden – log ind og deltag i debatten