782 - logica

Indovina il numero

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?

   

   

Problema tratto dal test di ingresso PRIMES del 2014; immagine di GDJ, da OpenClipArt.