Raad het getal

Raad het getal is een spel voor twee personen waarbij iemand één geheel getal bedenkt, dat de ander vervolgens gaat raden. Diegene die het getal bedenkt, noemen we de bedenker en diegene die gaat raden de speler.

Het spel werkt als volgt: De bedenker kiest een getal van maximaal vier cijfers, waarbij het eerste cijfer geen 0 mag zijn. Het getal kan dus bijvoorbeeld 7 zijn, of 60, of 544, of 9328.

Vaak kiest de bedenker een viercijferig getal dat makkelijk te onthouden is. Dat is een getal dat

• bestaat uit vier dezelfde cijfers, of
• bestaat uit vier opeenvolgende cijfers, die in oplopende of aflopende volgorde staan (bijvoorbeeld 2345 of 4321).

Bereken hoeveel verschillende makkelijk te onthouden getallen er zijn.

Het getal dat de bedenker bedenkt, noemen we het bedachte getal. De getallen die de speler noemt, noemen we genoemde getallen.

Omdat het lang kan duren voordat de speler het bedachte getal noemt, geeft de bedenker feedback. Deze feedback bestaat uit een van de volgende drie mogelijkheden:

1. 'Goed geraden' (bedachte getal = genoemde getal).
2. 'Hoger' (bedachte getal > genoemde getal).
3. 'Lager' (bedachte getal < genoemde getal).

Het noemen van een getal en het geven van feedback herhaalt zich totdat de bedenker de feedback 'Goed geraden' geeft en het spel stopt. Het aantal keer dat de speler een getal noemt en vervolgens feedback krijgt, noemen we het aantal beurten.

We bekijken eerst een vereenvoudigde versie van het spel, waarbij de speler aan het begin van het spel weet dat het bedachte getal minimaal 1 is en maximaal 9. De speler kan in elke beurt het aantal nog mogelijke getallen in ieder geval halveren door de volgende strategie toe te passen:

• Is het aantal nog mogelijke getallen oneven, noem dan het middelste nog mogelijke getal.
• Is het aantal mogelijke getallen even, noem dan een van de twee middelste nog mogelijke getallen.

De bedenker kiest het getal 8. De speler volgt bovenstaande strategie.

Het aantal beurten waarin de speler het bedachte getal raadt, ligt dan nog niet vast.

Onderzoek welke aantallen beurten mogelijk zijn waarin de speler het bedachte getal 8 kan raden.

In het vervolg van deze opgave bekijken we een versie van het spel, waarbij we de eis dat het bedachte getal uit maximaal vier cijfers moet bestaan, loslaten. We kijken naar getallen tussen 0 en $n$, waarbij $n$ een geheel getal groter dan 1 is. Hierdoor kan het bedachte getal elk getal vanaf 1 tot en met $n-1$ zijn.

Het aantal beurten dat nodig is om het bedachte getal te raden, hangt mede af van de gevolgde strategie. Als de eerder beschreven strategie toegepast wordt, dan geldt:

$$n-1 < 2^{m-1}$$

Hierbij is $m$ het maximaal aantal beurten dat nodig is om het bedachte getal te noemen.

Twee personen spelen het spel met $n=26$. Volgens de formule is de kleinst mogelijke waarde van $m$ dan gelijk aan 6.

Toon dit met behulp van de formule $n-1 < 2^{m-1}$ aan.

De waarde 6 die de formule geeft voor $n=26$ gaat uit van het 'slechtste' geval: dat steeds precies de helft van het aantal mogelijke getallen overblijft. Het blijkt echter dat voor $n=26$ de speler het bedachte getal altijd in maximaal 5 beurten kan noemen.

Bepaal het maximaal aantal overblijvende getallen per beurt en laat daarmee zien dat de speler in maximaal 5 beurten het bedachte getal kan noemen voor $n=26$.