782 – logica

Conoscete sicuramente il gioco “indovina un numero (naturale) facendo solo domande con risposta sì oppure no”: la strategia ottimale consiste nel dividere a metà l’intervallo possibile. Così, se il numero è compreso tra 1 e 1024, la prima domanda sarà “Il numero è tra 1 e 512?” Se la risposta è affermativa, la seconda domanda sarà “Il numero è tra 1 e 256?”, altrimenti sarà “Il numero è tra 513 e 768?”. Supponiamo ora che il nostro interlocutore abbia il diritto – ma non l’obbligo! – di mentire al più una sola volta. Riuscite a scoprire un numero compreso tra 1 e 2¹⁶ in al più 21 tentativi?


(trovate un aiutino sul mio sito, alla pagina https://xmau.com/quizzini/p782.html; la risposta verrà postata lì il prossimo mercoledì. Problema tratto dal test di ingresso PRIMES del 2014; immagine di GDJ, da OpenClipArt.)