Gioco

Domande[modifica | modifica wikitesto]

Penso ad un numero tra 0 e 15. Facendomi le 7 domande che seguono, a cui posso rispondere sì o no, una persona è in grado non solo di indovinare il numero che ho pensato, ma anche di capire se a una delle sette domande ho detto una bugia. Le possibili risposte totali sono . In base alle regole del gioco ho otto possibilità (o non dico bugie, oppure ne dico una ad una sola delle sette domande).


Le domande sono le seguenti:

  1. ?
  2. è uno tra i seguenti numeri: ?
  3. è uno tra i seguenti numeri: ?
  4. è dispari?
  5. è uno tra i seguenti numeri: ?
  6. è uno tra i seguenti numeri: ?
  7. è uno tra i seguenti numeri: ?


Indico le risposte affermative con 1 e quelle negative con 0: se non ho detto bugie nelle prime 4 domande, si può risalire al numero che ho pensato perché la sua rappresentazione in base due si ottiene leggendo in ordine le cifre associate alle risposte alle prime quattro domande.


Prova: le risposte date dal concorrente alle domande sono . Se il giocatore non ha detto bugie, il numero che ha pensato ha come rappresentazione binaria , e quindi è 5. Verifico se questo è consistente con le risposte date alle domande successive, e questo non avviene perché se il numero fosse 5, la risposta alla domanda 6 dovrebbe essere sì.


Si può scoprire che il giocatore ha detto una bugia alla terza domanda, e quindi, correggendo la risposta a questa domanda, la rappresentazione binaria associata al numero è e il numero pensato è 7.

Trucco[modifica | modifica wikitesto]

Considero la matrice seguente:

(le righe sono i numeri da 1 a 7 in rappresentazione binaria)


Supponiamo di avere la seguente stringa di risposte:

  1. se non si sono dette bugie, il numero pensato è quello che in base 2 si scrive come , dove

sono i valori ottenuti nelle prime quattro domande

  1. Osservo che è un vettore con coefficienti in e tre componenti.

In questo caso

Se il vettore ottenuto è nullo, non ho detto bugie. Altrimenti si cerca in quale riga della matrice compare il vettore, quindi la bugia è stata detta alla quarta riga.

  1. In questo modo correggo l'errore e posso così risalire al numero guardandone la sua rappresentazione binaria.



Scelto il numero , denotiamo con il vettore che si ottiene rispondendo alle 7 domande senza dire nessuna bugia: questo vettore è tale che . Infatti è stata costruita in modo tale che moltiplicando uno dei vettori per per ottengo 0.


ha rango 3, quindi l'insieme dei vettori tali che è un sottospazio di di dimensione , e ha cardinalità (corrispondenti appunto ai numeri da 0 a 15).


Se un giocatore dice una bugia all'i-esima domanda, il vettore che viene dato al posto di è con vettore della base canonica.

perché . è l'i-esima riga di , e corrisponde quindi alla domanda in cui è stata detta la bugia.


Sia . Nota che:

  1. la somma di elementi di sta ancora in , perché è spazio delle soluzioni dell'equazione .
  2. Due elementi diversi di hanno coordinate che differiscono in almeno tre posizioni.
Dimostrazione

Se suppongo che quest'affermazione sia falsa, e cioè che differiscano in solo due coordinate, la i-esima e la j-esima, si avrebbe che , ma questo non può avvenire (intuitivamente corrisponde alle risposte date da un giocatore che dice una bugia all'i-esima domanda).

 
 PrecedenteSuccessivo