Visualizza un messaggio singolo
Vecchio 25-12-12, 16:55   #3
aspesi
Utente Super
 
L'avatar di aspesi
 
Data di registrazione: Nov 2009
Ubicazione: Terra dei Walser
Messaggi: 5,989
Predefinito Re: Un po' di calcoli ... un po' di logica....

Quote:
Supponiamo che ci siano 3 giocatori, ciascuno lancia una moneta e conosce solo l'esito (testa 0, croce 1) degli altri 2 lanci.
Esaminiamo i 4 casi con prevalenza di 0 (il resto è speculare), con le informazioni note a ciascun giocatore.

esito : 0 0 0 ! 1 0 0 ! 0 1 0 ! 0 0 1
1 G . : - 0 0 ! - 0 0 ! - 1 0 ! - 0 1
2 G . : 0 - 0 ! 1 - 0 ! 0 - 0 ! 0 - 1
3 G . : 0 0 - ! 1 0 - ! 0 1 - ! 0 0 -

Strategia: chi vede un numero di 0 pari a 2 dice che il suo numero è 1
A Natale si è tutti un po' più buoni....
Continuiamo l'esame del quiz.

E' stato trovato un metodo per aumentare la probabilità da 1/2 a 3/4 di vincere nel caso di 3 giocatori: Risponde solo chi vede "parità zero" (cioè 0 0 oppure 1 1 assegnati agli altri 2 giocatori, i quali passano vedendo invece 0 1 oppure 1 0)

In generale, la probabilità massima di vincere, possibile solo nel caso che il numero dei partecipanti sia P = 2^a - 1
con a = gruppi per la codifica = 2,3,4..., n
vale : probabilità = P/(P+1)

Come ci si può arrivare per P = 7 o 15 o 31, ecc..?

Prepariamo un codice per es. P = 7

1 .. 2 .. 3 .. 4 .. 5 .. 6 .. 7
.............. * .. * .. * .. * ... gruppo A
.... * .. * ............ * .. * ... gruppo B
* ....... * ....... * ....... * ... gruppo C

Ogni gruppo è costituito da 4 bit (quelli contrassegnati con l'asterisco) e occorre fare il controllo di parità della stringa di 7 bit, cioè contare il numero di 0 mod 2 all'interno di ogni gruppo, rispettivamente per i bit 4+5+6+7 (A), 2+3+6+7 (B) e 1+3+5+7 (C).

Solo il gruppo A ha parità errata? Allora il bit errato è il numero binario 1 0 0 = 4.
Si ha parità errata in B e C? Allora il bit errato è 0 1 1 = 3 ; ecc...ogni bit è univocamente identificato dal codice.

Modificando il bit errato si corregge la parità.
Strategia: ogni giocatore (numero 1 2 3 4 5 6 7 ) esegue il controllo di parità, contando il numero di 0 contenuto nei gruppi A B C sia ponendo alla posizione sua (che non conosce) il numero 1, sia ponendo il numero 0. Ricaverà due terne di bit.
Se una terna A B C così dedotta è 0 0 0 , allora deve rispondere (altrimenti passa).
E precisamente
Se vede parità 0 con 1 al posto corrispondente al suo numero, allora dice 0: viceversa se vede parità zero con il numero 0 al suo posto, allora dice 1.

Esempio, si abbia la stringa (completa) 0 1 0 1 0 0 1
La parità è:
A = 2 = 0
B = 2 = 0
C = 3 = 1
Si vede che risponderà il giocatore 1, che infatti calcolerà:
Ponendo 1 al posto 1: A=2=0; B=2=0; C=2=0 Parità 0 0 0 e dirà 0 e indovina
(Ponendo 0 al posto 1: A=2=0; B=2=0; C=3=1 Controllo 0 0 1 che è la sua posizione)
Nessuno degli altri giocatori avrà parità 0 0 0 e tutti gli altri diranno : passo!

A questo punto è facile scoprire chi risponderà (e dicendo cosa) nel caso si abbiano 15 giocatori, ai quali viene assegnata la stringa
1 0 0 | 1 1 0 1 | 0 0 0 1 | 1 1 1 0

E inoltre cosa dice ogni giocatore per quest'altra:
1 1 1 | 1 1 0 1 | 0 1 1 1 | 1 1 0 1

Mi scuso se l'esposizione risulta poco chiara... ma oggi è Natale


Ultima modifica di aspesi : 25-12-12 16:57.
aspesi non in linea   Rispondi citando