Digressione: gioco ALTO/BASSO

Si tratta di indovinare un numero \( x \) tra 1 e 999. Ad ogni tentativo \( n \) l'avversario deve dire se \( x \geq n \) (ALTO) o se \( x \lt n \) (BASSO).

Quanti tentativi devo fare se uso la strategia ottimale?























Risposta: 10

Il gatto di Schrödinger

(ovvero: il mio avversario è un truffatore)

Se il mio avversario modifica il numero \( x \) che aveva scelto durante il gioco (senza farsi scoprire!) non potrò contare sulla fortuna. Se il mio primo tentativo è troppo sbilanciato (ad esempio provo con \(n = 200 \) sperando che la scelta di \( x \) sia piccola), l'avversario risponderà BASSO e cambierà \( x \) in un valore tra superiore a 200.

In modo equivalente possiamo pensare ad una sovraposizione quantistica un po' come nel famoso esempio del gatto di Schrödinger, che è simultaneamente vivo e morto finché non faccio un esperimento che fa collassare la situazione, ad esempio aprendo la scatola.

Tutti i valori ammissibili di \( x \) convivono in uno stato di sovrapposizione ed ogni successivo tentativo di indovinare riduce l'insieme di tali valori in base alla risposta ALTO o BASSO.

Per prolungare il gioco l'avversario deciderà la risposta in modo da ridurre questo insieme il meno possibile.

Altri esempi binari

Teorema

Se il numero di possibili soluzioni è maggiore di \( 2^k \) allora non esiste una strategia che permetta sicuramente di concludere il gioco in al più \( k \) passi.

Dimostrazione

Infatti ci sono esattamente \( 2^k \) possibili sequenze di risposte SI/NO e per il principio della piccionaia ci sono due (o più) scelte della soluzione che provocano la stessa sequenza di risposte.

[Torna]