Gioco

Domande

Penso ad un numero $x$$x$ 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 $2^{7}$$2^{7}$. 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. $x>8$$x>8$?
2. $x$$x$ è uno tra i seguenti numeri: $4,5,6,7,12,13,14,15$$4,5,6,7,12,13,14,15$?
3. $x$$x$ è uno tra i seguenti numeri: $2,3,6,7,10,11,14,15$$2,3,6,7,10,11,14,15$?
4. $x$$x$ è dispari?
5. $x$$x$ è uno tra i seguenti numeri: $1,2,4,7,9,10,12,15$$1,2,4,7,9,10,12,15$?
6. $x$$x$ è uno tra i seguenti numeri: $1,2,5,6,8,11,12,15$$1,2,5,6,8,11,12,15$?
7. $x$$x$ è uno tra i seguenti numeri: $1,3,4,6,8,10,13,15$$1,3,4,6,8,10,13,15$?

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 $n,s,n,s,s,n,n$$n,s,n,s,s,n,n$. Se il giocatore non ha detto bugie, il numero che ha pensato ha come rappresentazione binaria $0101$$0101$, 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 è $0111$$0111$ e il numero pensato è 7.

Trucco

Considero la matrice seguente:

$$H={\begin{array}{ccc}0&0&1\\0&1&0\\0&1&1\\1&0&0\\1&0&1\\1&1&0\\1&1&1\end{array}}$$

$$H={\begin{array}{ccc}0&0&1\\0&1&0\\0&1&1\\1&0&0\\1&0&1\\1&1&0\\1&1&1\end{array}}$$

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

Supponiamo di avere la seguente stringa di risposte: $B=(1,0,1,0,0,1,0)$$B=(1,0,1,0,0,1,0)$

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

sono i valori ottenuti nelle prime quattro domande

1. Osservo che $B\times H$$B\times H$ è un vettore con coefficienti in $\mathbb {Z} _{2}$$\mathbb {Z} _{2}$ e tre componenti.

In questo caso

$$B\times H=(1,0,0)$$

$$B\times H=(1,0,0)$$

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 $x$$x$, denotiamo con $c_{x}$$c_{x}$ il vettore che si ottiene rispondendo alle 7 domande senza dire nessuna bugia: questo vettore è tale che $c_{x}\times H=0$$c_{x}\times H=0$. Infatti $H$$H$ è stata costruita in modo tale che moltiplicando uno dei vettori $c_{x}$$c_{x}$ per $x=0,1,\dots ,15$$x=0,1,\dots ,15$ per $H$$H$ ottengo 0.

$H$$H$ ha rango 3, quindi l'insieme dei vettori $v$$v$ tali che $v\times H=0$$v\times H=0$ è un sottospazio di $(\mathbb {Z} _{2})^{7}$$(\mathbb {Z} _{2})^{7}$ di dimensione $7-3=4$$7-3=4$, e ha cardinalità $2^{4}=16$$2^{4}=16$ (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 $c_{x}$$c_{x}$ è $c_{x}+e_{i}$$c_{x}+e_{i}$ con $e_{i}$$e_{i}$ vettore della base canonica.

$$(c_{x}+e_{i})\times H=c_{i}H+e_{i}H=e_{i}H$$

$$(c_{x}+e_{i})\times H=c_{i}H+e_{i}H=e_{i}H$$

perché $c_{x}H=0$$c_{x}H=0$. $e_{i}H$$e_{i}H$ è l'i-esima riga di $H$$H$, e corrisponde quindi alla domanda in cui è stata detta la bugia.

Sia $C=\{c_{0},c_{1},\dots ,c_{15}\}$$C=\{c_{0},c_{1},\dots ,c_{15}\}$. Nota che:

1. la somma di elementi di $C$$C$ sta ancora in $C$$C$, perché $C$$C$ è spazio delle soluzioni dell'equazione $v\times H=0$$v\times H=0$.
2. Due elementi diversi di $C$$C$ hanno coordinate che differiscono in almeno tre posizioni.

Dimostrazione

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