Consideriamo il gioco Indovina numero. Un giocatore A pensa e scrive su un foglio un numero intero che può andare da 0 a 100. Un altro giocatore B tenta di indovinare il numero. Ad ogni tentativo A deve dire a B se ha indovinato il numero (e in tal caso la partita è finita), se l'ha superato o se è rimasto al di sotto. Nelle partita successiva A e B invertono i ruoli. E così via. Alla fine vince chi ha fatto complessivamente meno tentativi a vuoto. Le istruzioni numerate seguenti rappresentano la strategia più elementare che si può seguire (abbiamo indicato con X il numero da indovinare):
1. | Devo cercare un numero compreso tra N1 e N2. N1 è 0 e N2 è 100. |
2. | Dico un numero N compreso tra N1 e N2. |
3. | Se X = N la partita è finita. |
4. | Se X > N restringo la zona di ricerca a destra di N, cioè prendo N come nuovo N1, altrimenti restringo la ricerca a sinistra di N, cioè prendo N come nuovo N2. |
5. | Ripeto a partire dall'istruzione 2. |
Prova a trovare una strategia più efficiente, che non si limiti a prendere un numero qualunque compreso tra N1 e N2.
L'idea del procedimento è quella di far tesoro degli insuccessi: se X è
maggiore del numero che ho detto è inutile che nei successivi
tentativi dica numeri più piccoli; analogamente se X è
minore del numero che ho detto è inutile poi tentare con
numeri più grandi.
Se ci si riflette, si capisce facilmente che
conviene precisare il passo 2:
dico N che stia a metà
tra N1 e N2 (a seconda dei casi di N ce n'è 1 o ce ne sono 2). Ovvero:
considero M = (N1+N2)/2; se M è intero prendo N = M, altrimenti prendo come N l'intero immediatamente precedente o immediatamente successivo.
Domanda Se vi trovate di fronte a un
avversario che sceglie questa strategia, quale numero vi conviene
pensare?
(si possono pensare ad esempio 0, 100, 49, , che comportano il massimo numero di tentativi)