Discussioni sulla risoluzione di giochi matematici.
25/05/2018, 18:29
Ci sono due prigionieri, A e B, di fronte a una stanza chiusa. Il carceriere (un po' sadico, tanto per cambiare) propone loro il seguente gioco per guadagnarsi la liberertà: dapprima, A entra nella stanza, dove c'è un certo numero di monete disposte in fila su un tavolo, che mostrano testa oppure croce. Il carceriere gliene indica una, dopodiché A deve voltare una e una sola delle monete sul tavolo (cioé farla passare da testa o croce o viceversa). Infine, A esce dalla stanza e B vi entra. I prigionieri vincono se B riesce a indovinare la moneta indicata ad A dal carceriere. Ovviamente non è permessa nessuna comunicazione fra i prigionieri durante lo svolgimento del gioco.
Come al solito, A e B possono mettersi d'accordo su una strategia di gioco prima di intraprendere la partita. Dimostrare che esiste una strategia vincente se e solo se il numero di monete sul tavolo è una potenza di 2.
25/05/2018, 22:53
Avrei trovato uno schema con quattro monete ...
26/05/2018, 08:28
C'entrano qualcosa i numeri binari?
26/05/2018, 11:07
con 3 monete esiste una strategia vincente
26/05/2018, 12:24
dan95 ha scritto:C'entrano qualcosa i numeri binari?
Testo nascosto, fai click qui per vederlo
yes! almeno per la direzione del "se".
Settevoltesette ha scritto:con 3 monete esiste una strategia vincente
No... ricorda che A deve necessariamente girare una moneta.
27/05/2018, 07:16
La butto lì...
Testo nascosto, fai click qui per vederlo
Se ci sono $2^n$ monete allora abbiamo $2^(2^n)$ numeri binari corrispondenti, per esempio, se le monete sono 4 avremo 16 possibili configurazioni (numeri binari)
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Ora i due prigionieri si accordano sul fatto che 0=testa e 1=croce, a questo punto i $2^(2^n)$ numeri binari vengono suddivisi in $2^(2^n-n)$ stringhe lunghe $2^n$ numeri e ogni numero della stringa viene fatto identificare ad un numero da 1 a $2^n$ (senza ripetizioni) in modo che cambiando un solo 0 o 1 in un numero binario appartenente ad una stringa possono ottenere un un numero binario appartenente ad un'altra stringa che identifica un qualsiasi numero da 1 a $2^n$.
27/05/2018, 09:57
dan95 ha scritto:La butto lì...
Testo nascosto, fai click qui per vederlo
Se ci sono $2^n$ monete allora abbiamo $2^(2^n)$ numeri binari corrispondenti, per esempio, se le monete sono 4 avremo 16 possibili configurazioni (numeri binari)
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Ora i due prigionieri si accordano sul fatto che 0=testa e 1=croce, a questo punto i $2^(2^n)$ numeri binari vengono suddivisi in $2^(2^n-n)$ stringhe lunghe $2^n$ numeri e ogni numero della stringa viene fatto identificare ad un numero da 1 a $2^n$ (senza ripetizioni) in modo che cambiando un solo 0 o 1 in un numero binario appartenente ad una stringa possono ottenere un un numero binario appartenente ad un'altra stringa che identifica un qualsiasi numero da 1 a $2^n$.
Uhm, non so se ho capito bene... Non dovresti comunque dimostrare che le configurazioni si incastrano bene? Cioé che per ogni $n$ e $m$, si può passare da una configurazione associata alla moneta $n$ a una associata alla moneta $m$ girando una sola moneta?
27/05/2018, 13:47
Sì...ecco perché ho scritto "La butto lì", ci penso con più calma perché adesso come adesso non mi viene la dimostrazione.
28/05/2018, 14:37
Penso...
Testo nascosto, fai click qui per vederlo
Siccome per n >2 vale $2^(2^n-n)>2^n$, i $2^(2^n-n)$ blocchi contengono ciascuno $2^n$ numeri binari, ognuno dei quali codifica uno ed un solo numero (posizione della moneta) tra 1 e $2^n$. Ora, siccome il numero dei blocchi è maggiore del numero di possibili posizioni delle monete che possono essere scelte posso associare ad un binario $b_0$ che codifica un numero tra $1$ e $2^n$ di un blocco $m$ un binario $b_1$ di un'altro blocco $n$ ottenuto dal primo cambiando un 1 o 0 che codifica un altro numero $1$ tra $2^n$, poi un binario $b_2$, $b_3$ e così via fino a $b_{2^n}$ ... non so se mi sono spiegato bene...
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.