Impariamo a cercare, ovvero l'arte di spaccare il capello in quattro

In un post precedente, abbiamo introdotto gli elementi di base della teoria dei grafi. Abbiamo detto che un grafo è un insieme di nodi connessi da archi e che con i grafi si possono costruire modelli di un numero considerevole di realtà quotidiane.

Oggi vediamo un giochino semplice semplice e la prossima volta ne costruiremo il modello mediante la teoria dei grafi. Allora, il giochino è questo: pensate un numero tra 0 e 1000. Quanti tentativi occorrono, secondo voi, perché io lo indovini ? Vi chiedo solo un piccolo aiutino: ogni volta che faccio un tentativo dovete solamente dirmi se il vostro numero è maggiore o minore di quello che vi ho proposto.

Certo 1000 è una bella cifra, se iniziassi da zero e aumentassi di 1 e il vostro fosse un numero alto ci vorrebbero centinaia di tentativi prima che io azzecchi. E se, invece vi proponessi numeri a caso di volta in volta ? Anche in questo caso si rischierebbe di impiegare diverse centinaia di tentativi…. come fare ?

Vi stupireste se vi dicessi che qualsiasi numero sia io lo azzecco in massimo 10 tentativi ? Magia ? Imbroglio ? Gioco di prestigio ? Nulla di tutto ciò ovviamente, solo un modello matematico semplice e raffinatissimo…

Facciamo un caso pratico (al limite della schizofrenia perché richiede uno sdoppiamento di personalità, ma tant’è …), diciamo che il numero da voi pensato è 716.

Vediamo se è vero che lo possiamo indovinare in al più 10 tentativi:

– Io (Tentativo numero 1): io dico che il numero è 500, voi che mi dite ?

(si lo so che è un dialogo schizofrenico ma mi raccomando non ditelo al mio dottore !)

– Voi: uhmmmm…. 716 è più grande di 500, quindi dico: MAGGIORE

– Io: (Tentativo numero 2) ok, è maggiore, quindi io dico 750.

– Voi: allora … secondo me Carlo stai barando perché ti sei avvicinato troppo ! Fai finta di non saperlo e poi invece … ma stiamo al gioco: 716 è più piccolo di 750 …. MINORE !

– Io: (Tentativo numero 3) ah, si ? Allora io dico 625.

-Voi: ué, ti sei allontanato, c’eri andato così vicino: 716 e più grande di 625: MAGGIORE

– Io (e 4): vediamo, maggiore …. 688 !

– Voi: MAGGIORE! adesso che fai imbrogli al contrario ? aumenta dai …

– Io (siamo a 5): ah si … 719 !
– aaaahhh lo vedi che imbrogli ? Minore !

– Io (6 ): 704
– Maggiore …

– Io (7): 712
– Maggiore !

– Io (ottavo ed ultimo tentativo): 716 !
– Voi: hai indovinato, ma hai barato …

Grazie della fiducia, eh ! No, non ho barato, ho semplicemente usato l’algoritmo che va sotto il nome di ricerca dicotomica o algoritmo di bisezione. Ad ogni tentativo ho proposto il numero esattamente alla metà del massimo e del minimo numero possibile.

All’inizio, quando il gioco è cominciato il minimo ed il massimo sono 0 e 1000, quindi il numero che sta esattamente in mezzo tra di loro è 0 più 1000 diviso 2, uguale 500. Quando mi avete detto che il numero è maggiore, il nuovo minimo è diventato 500 e il massimo è restato 1000, quindi al tentativo successivo vi ho proposto 1000 più 500 diviso 2 uguale 750, che poi è diventato il nuovo massimo e così via.

Si dimostra che procedendo per bisezione il numero massimo di tentativi per indovinare un numero compreso tra 0 e 1000 è pari proprio a 10. Non male no ?

Come si dimostra, dite ? Lo vediamo la prossima volta usando i grafi, intanto potete divertirvi a scommettere con i vostri amici e farvi pagare la colazione o merenda che sia …