Tænk på et tal mellem 1 og 1000. Jeg skal nu gætte dit tal. Hvor mange gæt skal jeg bruge?

Ja, nu er spørgsmålet jo, hvordan du svarer - hvis du bare siger “rigtigt/forkert” så skal jeg jo i sagens natur bruge 1000 gæt hvis jeg skal være HELT sikker på at jeg kan gætte det, hver gang vi leger, fordi jeg ikke får anden information af dit svar end om mit gæt var rigtigt eller forkert.

Hvis du derimod er flink nok til at svare “Nej, mit tal er højere” eller “Nej, mit tal er lavere”, når jeg gætter forkert, hvor mange gæt skal jeg så bruge?

Faktisk skal jeg kun bruge 10 gæt under de omstændigheder, hvis jeg ellers vælger min spørgestrategi med omhu.

Eksempel

Du tænker på tallet 395.
Jeg gætter: 500
Du svarer: Lavere
Jeg gætter: 250
Du svarer: Højere
Jeg gætter: 375
Du svarer: Højere
Jeg gætter: 438
Du svarer: Lavere
Jeg gætter: 406
Du svarer: Lavere
Jeg gætter: 390
Du svarer: Højere
Jeg gætter: 398
Du svarer: Lavere
Jeg gætter: 394
Du svarer: Højere
Jeg gætter: 396
Du svarer: Lavere
Der er nu kun et tal tilbage, så jeg gætter: 395 og du er nødt til at svare: Korrekt.

Det var det tiende gæt, og det er muligt at vise at man aldrig skal bruge flere.

Metoden

Ideen er at udelukke så mange tal som muligt ved hvert gæt, og dette gøres lettest ved at halvere intervallet af de tilbageværende tal hver gang, og bruge det som det næste gæt.

Hvis mit første gæt er 500 har jeg allerede udelukket halvdelen af tallene, når jeg fx får at vide at dit tal er lavere. Mit næste gæt vil nu være 250, for det er midten af det nye interval, og hvis du nu siger “Højere”, så har jeg kun intervallet 250–500 tilbage.

På to gæt har jeg reduceret antallet af muligheder til en fjerdedel. Hvis jeg fortsætter på denne måde med at gætte på det midterste tal i intervallet, vil jeg jo halvere mængden af mulige tal hver gang, og dermed vil listen over mulige tal udvikle sig således: 1000, 500, 250, 125, 63, 32, 16, 8, 4, 2, 1.

Der vil altså altid kun være et muligt tal tilbage efter 10 gæt, og det vil være tallet du tænkte på.

Den vågne nørd vil nu have bemærket at talserien minder meget om potenser af 2, og det er jo heller ikke så mærkeligt, idet man deler med 2 hver gang, og efter 10 gæt har man altså delt intervallet 1–1000 ned i \(2^{10}=1024\) mindre dele og nøjagtigheden på gættene er således cirka 1 — i hvert fald tæt nok på til at man kan ramme rigtigt. Keine hexerei, nur behändigkeit.

\Worm