Divinazione binaria
La divinazione binaria è un gioco matematico automatico per indovinare un numero, tramite alcune domande prefissate che si basano sul sistema binario.
Funzionamento modifica
Scelto un numero all'interno di un intervallo, ogni domanda è nascostamente volta ad individuare una cifra della sua scrittura in base 2. Le domande sono poste in modo implicito e chiedono semplicemente se il numero appartiene ad un dato insieme.
La successione di risposte "sì" e "no" per le domande fornisce quindi la scrittura binaria in "1" e "0" per il numero da indovinare. Senza bisogno di conoscere la scrittura in base 2, il numero può essere ottenuto attribuendo ad ogni domanda un "valore" doppio della precedente: la prima domanda vale 1, la seconda 2, la terza 4, la quarta 8, e così via. Sommando le domande a cui è stata data una risposta positiva si trova il numero da indovinare.
Più precisamente, la prima domanda chiede se il numero sia pari o dispari, ovvero se la sua scrittura binaria finisca con 0 o con 1. La seconda domanda chiede se il numero è del tipo 4k o 4k+1 oppure del tipo 4k+2 o 4k+2+1, quindi se la sua penultima cifra, sempre in base due, sia 0 o 1. Ogni domanda successiva scopre una nuova cifra. Con n domande è quindi possibile scoprire un qualunque numero scelto a caso nell'intervallo tra 0 e (la cui scrittura in base binaria è 11...11, con la cifra 1 ripetuta n volte). Viceversa, per indovinare un numero tra 0 e N servono almeno domande.
Esempio di gioco modifica
Per indovinare un numero compreso tra 0 e 15 bastano quattro domande che, secondo questo metodo, chiedono se il numero sia compreso o meno nei seguenti insiemi:
| prima domanda (valore 1) | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | |||||||
| seconda domanda (valore 2) | 2 | 3 | 6 | 7 | 10 | 11 | 14 | 15 | |||||||
| terza domanda (valore 4) | 4 | 5 | 6 | 7 | 12 | 13 | 14 | 15 | |||||||
| quarta domanda (valore 8) | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
Con il numero 11, per esempio, le risposte nell'ordine saranno: sì, sì, no, sì. Sommando dunque i valori corrispondenti ad ogni domanda si ottiene esattamente 1+2+8 = 11.
Varianti modifica
Applicando una permutazione ai numeri dell'intervallo, è possibile assegnare ad ogni numero un diverso "codice" di zeri e uni, ovvero di risposte affermative e negative. In questo modo si possono ottenere tutti i sistemi che permettono di indovinare il numero utilizzando un numero minimo di domande prefissate: tramite ogni domanda è infatti possibile escludere (circa) metà dei numeri e ridurre di (circa) metà l'insieme in cui si trova il numero da indovinare.
Una versione più complicata di questo gioco permette all'inerlocutore di mentire ad un certo numero di domande, ma per questo è necessario introdurre alcune domande ridondanti. Questa variante si basa sugli algoritmi informatici per la ricostruzione di dati compromessi in una trasmissione, alla base del RAID.[senza fonte]
