Divinazione binaria

Questa voce o sezione sull'argomento Matematica è priva o carente di note e riferimenti bibliografici puntuali.

---

Sebbene vi siano una bibliografia e/o dei collegamenti esterni, manca la contestualizzazione delle fonti con note a piè di pagina o altri riferimenti precisi che indichino puntualmente la provenienza delle informazioni. Puoi migliorare questa voce citando le fonti più precisamente. Segui i suggerimenti del progetto di riferimento.

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

La divinazione binaria è un gioco matematico automatico per indovinare un numero, tramite alcune domande prefissate che si basano sul sistema binario.

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 ${\displaystyle 2^{n}-1}$ (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 ${\displaystyle \log _{2}(N+1)}$ domande.

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:

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.

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]}

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica