Indovina il numero

Dite di considerare l'espansione binaria del numero, eventualmente riempendola a sinistra con degli zeri per arrivare a sedici cifre. Le prime 15 domande sono "La cifra in posizione n è uno zero?", mentre la sedicesima è "Hai mentito a una delle domande precedenti"? Se ha effettivamente mentito, deve rispondere sì, perché non può mentire più di una volta. Se non ha mentito, può rispondere sì (è la sua bugia) oppure no. Se la risposta è sì, siamo certi che abbia già mentito; possiamo quindi usare una ricerca binaria per scoprire su quale domanda ha mentito (quattro domande in tutto), e se non ha mentito su nessuna usare la ventunesima domanda per scoprire l'ultima cifra. Se la risposta è no, le prime quindici cifre sono corrette, e possiamo chiedere per tre volte qual è la sedicesima, prendendo come risposta quella data almeno due volte.

Un'ultima parola

Sapere che può essere detta una sola bugia semplifica molto la vita.