Prigionieri e monete

Messaggioda Vincent46 » 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.
Vincent46
Average Member
Average Member
 
Messaggio: 197 di 523
Iscritto il: 26/01/2014, 17:27

Re: Prigionieri e monete

Messaggioda axpgn » 25/05/2018, 22:53

Avrei trovato uno schema con quattro monete ...
axpgn
Cannot live without
Cannot live without
 
Messaggio: 11195 di 40641
Iscritto il: 20/11/2013, 22:03

Re: Prigionieri e monete

Messaggioda dan95 » 26/05/2018, 08:28

C'entrano qualcosa i numeri binari?
"Chi è padrone del proprio respiro, è padrone della propria vita."~ Antico proverbio

"La capacità di scegliere è un dono che la natura fa all'uomo. Scegliere è un dono che l'uomo fa a se stesso." D.B.

"Il genio è semplicemente un uomo con la mente da donna." D. B.
dan95
Cannot live without
Cannot live without
 
Messaggio: 2253 di 5268
Iscritto il: 10/06/2013, 16:37
Località: Roma Caput Mundi

Re: Prigionieri e monete

Messaggioda Settevoltesette » 26/05/2018, 11:07

con 3 monete esiste una strategia vincente
Settevoltesette
Average Member
Average Member
 
Messaggio: 42 di 682
Iscritto il: 07/04/2018, 16:06

Re: Prigionieri e monete

Messaggioda Vincent46 » 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.
Vincent46
Average Member
Average Member
 
Messaggio: 198 di 523
Iscritto il: 26/01/2014, 17:27

Re: Prigionieri e monete

Messaggioda dan95 » 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$.
"Chi è padrone del proprio respiro, è padrone della propria vita."~ Antico proverbio

"La capacità di scegliere è un dono che la natura fa all'uomo. Scegliere è un dono che l'uomo fa a se stesso." D.B.

"Il genio è semplicemente un uomo con la mente da donna." D. B.
dan95
Cannot live without
Cannot live without
 
Messaggio: 2257 di 5268
Iscritto il: 10/06/2013, 16:37
Località: Roma Caput Mundi

Re: Prigionieri e monete

Messaggioda Vincent46 » 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?
Vincent46
Average Member
Average Member
 
Messaggio: 200 di 523
Iscritto il: 26/01/2014, 17:27

Re: Prigionieri e monete

Messaggioda dan95 » 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.
"Chi è padrone del proprio respiro, è padrone della propria vita."~ Antico proverbio

"La capacità di scegliere è un dono che la natura fa all'uomo. Scegliere è un dono che l'uomo fa a se stesso." D.B.

"Il genio è semplicemente un uomo con la mente da donna." D. B.
dan95
Cannot live without
Cannot live without
 
Messaggio: 2259 di 5268
Iscritto il: 10/06/2013, 16:37
Località: Roma Caput Mundi

Re: Prigionieri e monete

Messaggioda dan95 » 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...
"Chi è padrone del proprio respiro, è padrone della propria vita."~ Antico proverbio

"La capacità di scegliere è un dono che la natura fa all'uomo. Scegliere è un dono che l'uomo fa a se stesso." D.B.

"Il genio è semplicemente un uomo con la mente da donna." D. B.
dan95
Cannot live without
Cannot live without
 
Messaggio: 2262 di 5268
Iscritto il: 10/06/2013, 16:37
Località: Roma Caput Mundi

Re: Prigionieri e monete

Messaggioda nino_ » 28/05/2018, 22:39

nino_
Average Member
Average Member
 
Messaggio: 481 di 976
Iscritto il: 13/10/2014, 15:17

Prossimo

Torna a Giochi matematici

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite