Ancora nanetti e cappelli.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

7 nanetti vengono rapiti. La strega cattiva gli mette in testa dei cappelli neri o bianchi con probabilità 1/2. Ciascun nanetto vede il colore dei cappelli di tutti gli altri ma non il proprio!
I nanetti dopo aver visto i cappelli di tutti, e senza poter comunicare in alcun modo tra loro, dovranno scrivere su un foglietto personale una delle seguenti tre cose: "Nero", "Bianco" oppure "Non lo so".
I nanetti si salvano se: Almeno un nanetto indovina il proprio colore e nessun nanetto sbaglia il proprio colore.
I nanetti muoiono se: Almeno un nanetto sbaglia il proprio colore oppure se scrivono tutti "non lo so".

Trovare una strategia tale per cui i nanetti si salvano a meno che tutti i cappelli non siano bianchi.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Edited:
[ot]Ho capito solo ora cosa intendi con "in mezzo"...

"axpgn":Mamma mia, è incredibile, non ci posso credere!

Il primo esce.
Il secondo esce e si mette accanto al primo.
Il terzo esce e se vede cappelli tutti dello stesso colore si mette accanto agli altri mentre se vede cappelli di colore diverso si mette in mezzo
E così tutti gli altri.

Non ti bastava così?

Cordialmente, Alex

Ecco perché la risposta alla domanda "Non ti bastava così?" È No!

Mentre ho definito esattamente la posizione in cui si mette con questo papiro

"3m0o":Penso che così funzioni

Il primo esce e si mette, diciamo, tutto a sinistra. Il secondo esce e si mette alla sua destra lasciando sufficiente spazio in mezzo a loro. Il terzo nanetto ora esce e vede due casi possibili.
3.1) Se i colori del primo e del secondo sono uguali allora si metterà alla destra del secondo.
3.2) Se i colori sono distinti si mette in mezzo tra i due.

Il quarto nanetto che esce fa una delle seguenti cose:
4.1) Se vede i colori dei 3 che sono tutti uguali allora si metterà alla destra del terzo.
4.2) Se vede due colori allora almeno 2 sono uguali, diciamo rosso, e si metterà in mezzo tra il terzo e quello con il colore azzurro.

Step \( k \): Sia \(m_k\) il \(k\)-esimo nanetto ad uscire. Con \( k \geq 3 \) abbiamo che lo step \(k\) è quando \(m_k\) deve uscire.
Sia quindi in altre parole \( m_j\) una numerazione dei nanetti secondo l'ordine cronologico di uscita. Quindi \(m_1\) è il primo ad essere uscito, \(m_2\) il secondo. Etc.
Ad ogni step sia \(n_j(k)\) una ri-numerazione dei nanetti - che dipende da \(k\) - già fuori e in fila uno accanto all'altro. La definiamo nel seguente modo: \(n_1:=m_1\) è il nanetto più a sinistra, se \(n_j \) è già stato definito allora \(n_{j+1} \) è il nanetto subito alla sua destra, con \(1 \leq j \leq k-1\). Cosicché \(n_{k-1} \) risulta essere il nanetto più a destra. In altro modo è una numerazione posizionale allo step \(k\).
NB: Abbiamo che \(n_2(2) = m_2 \) ma ad esempio è possibile che \(n_2(3) = m_3 \) e \( n_3(3)=m_2\) così come è possibile che \( n_2(3)=m_2 \) e \(n_3(3)=m_3\).

Sia \( \operatorname{cl} : \{m_1,m_2,\ldots \} \to \{ r,a\} \) la funzione che preso un nanetto restituisce il colore del suo cappello. Sia \( M_k:= \{ m_1 ,\ldots, m_{k-1} \} \) l'insieme dei nanetti già fuori e siano \( A_k = \{ m \in M_k : \operatorname{cl}(m) = a \} \) e \( R_k = \{ m \in M_k : \operatorname{cl}(m) = r \} \) gli insiemi dei nanetti con i cappelli azzurri e rossi rispettivamente..
Sia \( s=s(k) \) il \(k\)-esimo indice di separazione, i.e. \( 1 \leq s \leq k-1 \) tale che wlog \( A_k = \{ n_1(k) , \ldots, n_s(k) \} \) e \( R_k = \{ n_{s+1}(k) , \ldots, n_{k-1}(k) \} \), dove se \(s=k-1 \) allora \(R_k = \emptyset\).

A.1) Se \( s< k-1 \) allora \(m_k \) si posizionerà tra \(n_s(k) \) e \(n_{s+1}(k) \).

A.2) Se \( s= k-1 \) allora \(m_k\) si posizionerà a destra di \(n_s(k) \), i.e. \( n_k(k+1)=m_k \).



Quello che sostanzialmente facciamo ad ogni step è aggiungere \(m_k \) al buon insieme, i.e. quel insieme tale che \( A_{k+1} = A_k \cup \{ m_k \} \) (risp. \( R_{k+1} = R_k \cup \{ m_k \} \)) rispettando l'ordine posizionale interno dei due insiemi, dove \(m_k \) sarà il più a destra di \(A_{k+1} \) o il più a sinistra di \(R_{k+1}\) ad ogni step.

Poi che si poteva essere più concisi sono d'accordo


Comunque sia allora non cambia proprio nulla rispetto la risposta a questo

"axpgn":

[quote="3m0o"]Infatti ad esempio il terzo a dipendenza di dove si mette sta comunicando agli altri un informazione! Ovvero "i vostri colori sono differenti" se si mette in mezzo oppure "i vostri colori sono uguali" se si mette a destra.

No, perché si mette SEMPRE in mezzo (pensaci )
Non sceglie MAI!

[axpgn]

[ot]

"3m0o":... perché lo fai apposta

Solo un pochino ...

Sempre "In mezzo" ossia tra i bianchi e i neri che funziona anche quando uno dei gruppi è vuoto.
Isn't it? [/ot]

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"3m0o":Trovare una strategia tale per cui i nanetti si salvano a meno che tutti i cappelli non siano bianchi.

Ho fatto un errore... postulo nuovamente la domanda perché ho sbagliato esponente ... infatti non è \( 2^{\text{numeri di nani}} -1 \) ma \( 2^k -1 = \text{numeri di nani} \) che sta a numeratore


Trovare la strategia ottimale

PS: Dai che vi ho già dato un mezzo hint così!

[hydro1]

Cioè quindi quanti se ne devono salvare?

[axpgn]

Tutti stando al post iniziale però l'hint non mi pare vada in quella direzione ... mah ...

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"hydro":Cioè quindi quanti se ne devono salvare?

No, cioè qual è la probabilità massimale che si salvano tutti, ad esempio se i nani sono \(n=1 ,2\) la probabilità massimale è \(p=1/2\). Se i nani sono \(n=3\), allora \(p=3/4\). Io chiedo con \(n=7\) quanto vale \(p\)? Come e perché? E la mia domanda iniziale era sbagliata perché (sbagliando esponente) pensavo fosse \(127/128\) ma è troppo alta!

"axpgn":Tutti stando al post iniziale però l'hint non mi pare vada in quella direzione ... mah ...

Non ho capito.

[axpgn]

Neanche noi!

Ovvero ci hai fatto diventare matti a cercare una strategia per cui TUTTI i nanetti si salvano ed invece volevi solo la massima probabilità con cui TUTTI si salvano

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"axpgn":Neanche noi!

Ovvero ci hai fatto diventare matti a cercare una strategia per cui TUTTI i nanetti si salvano ed invece volevi solo la massima probabilità con cui TUTTI si salvano

Mah... mi sembrava evidente che la domanda era probabilistica dicendo che tutti si salvano tranne con la disposizione particolare che erano tutti bianchi, infatti se fossero stati tutti bianchi non si sarebbero salvati e questa disposizione arrivava con probabilità \(1/128 \)... poi ho sbagliato la probabilità perché ci sono più casi in cui non si salvano... ma comunque sono sorprendentemente pochi

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Un grande Hint:

Supponiamo che i nanetti siano \(n=3\) in totale. Ho già detto che la strategia ottimale da una probabilità di successo ai nanetti pari a \(3/4\). Siccome i nanetti non hanno altre informazioni di quelle iniziali, e non hanno modo di guadagnare informazioni sul loro colore poiché il loro colore è indipendente dal colore degli altri! Chiaramente per avere più di \(1/2\) di probabilità e siccome basta che uno solo dica giusto e che nessuno sbagli per salvarsi, bisogna trovare una strategia che concentri l'errore in meno casi possibili. Ad esempio i nanetti potrebbero mettersi d'accordo e dirsi che se i colori fossero \( \{ 000,111 \} \) sbagliamo tutti in qualche modo e questo permette (in qualche modo) ad almeno un nano di indovinare (e a nessuno di sbagliare) se i loro cappelli sono differenti da quelli scelti.
La scelta dei casi in cui sbagliano però non è arbitraria. Possono ad esempio scegliere \( \{ 100, 011 \} \) ma non possono scegliere per esempio \( \{000,001\} \).

[axpgn]

Francamente sostenere che fosse evidente mi sembra una forzatura (eufemismo )
Scrivi che dobbiamo trovare una strategia per salvare i nanetti TRANNE in un caso, a me pare evidente dedurre che, tolto quel caso, la strategia per salvarli esiste, certa. IMHO.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Non vedi che hai detto la stessa cosa mia?
Tranne in un caso su 128 si salvano = probabilita di 127/128 di salvarli

[axpgn]

No, affatto.

Tolto quel caso la probabilità è $1$ quindi esiste sicuramente una strategia che li salva.
Questo dici nel post iniziale.

Poi invece chiedi di trovare una strategia che massimizzi la possibilità di salvarli che però è minore di $1$.

È molto diverso

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"axpgn":No, affatto.

Tolto quel caso la probabilità è $ 1 $ quindi esiste sicuramente una strategia che li salva.
Questo dici nel post iniziale.

Poi invece chiedi di trovare una strategia che massimizzi la possibilità di salvarli che però è minore di $ 1 $.

È molto diverso

No è la stessa cosa! Se ti chiedo di trovare una strategia che tolto un caso su \(128\) la probabilità di riuscita è \(1=127/127\), vuol dire che se includi quel caso allora la probabilità è \(127/128\) e questa pensavo fosse la probabilità ottimale che puoi ottenere con una strategia. In realtà siccome avevo sbagliato a fare i conti, la probabilità ottimale è un altra, ed è meno. Quindi ora ti chiedo di trovare una probabilità ottimale rispetto a tutti e \(128\) casi possibili che è equivalente a dire di trovare una strategia che li salvi tutti con probabilità \(1\) tolti un certo numero di casi possibili.

[axpgn]

Non c'è niente da fare, ci rinuncio ...

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

rinunci a cosa? A risolvere l'indovinello o non ho capito

[axpgn]

In quest'ultima risposta ammetti tu stesso che ci hai chiesto di trovare una strategia che li salvasse sicuramente tutti, una strategia che però NON esisteva ( ).

Quando te l'ho fatto notare

"axpgn":Neanche noi!

Ovvero ci hai fatto diventare matti a cercare una strategia per cui TUTTI i nanetti si salvano ed invece volevi solo la massima probabilità con cui TUTTI si salvano

mi hai risposto

"3m0o":Mah... mi sembrava evidente che la domanda era probabilistica ...

Se a te sembra la stessa cosa, va bene, alzo le mani ...

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Mi sa che non ci siamo semplicemente capiti, forse perché mi sono espresso male

Domanda originale

"3m0o":7 nanetti vengono rapiti. La strega cattiva gli mette in testa dei cappelli neri o bianchi con probabilità 1/2. Ciascun nanetto vede il colore dei cappelli di tutti gli altri ma non il proprio!
I nanetti dopo aver visto i cappelli di tutti, e senza poter comunicare in alcun modo tra loro, dovranno scrivere su un foglietto personale una delle seguenti tre cose: "Nero", "Bianco" oppure "Non lo so".
I nanetti si salvano se: Almeno un nanetto indovina il proprio colore e nessun nanetto sbaglia il proprio colore.
I nanetti muoiono se: Almeno un nanetto sbaglia il proprio colore oppure se scrivono tutti "non lo so".

Trovare una strategia tale per cui i nanetti si salvano a meno che tutti i cappelli non siano bianchi.

Ora ti spiego cosa intendevo dire:


Per semplicità di facciamo finta che i nanetti sono 2. Siccome i cappelli vengono messi con probabilità \(1/2\) abbiamo 4 possibili outcomes: (nero,nero), (bianco,bianco), (nero,bianco), (bianco,nero)
I nanetti non sanno in quale tra questi casi si trovano. Il compito originale era trovare una strategia che li salvasse con certezza tranne nel caso in cui i cappelli fossero stati tutti bianchi, ovvero:
-Si salvavano con certezza (probabilità \(1\)) nel caso in cui i cappelli fossero stati (nero,nero), (nero,bianco), (bianco, nero)
-Muoiono con certezza nel caso in cui i cappelli fossero stati (bianco, bianco)!!

Ovvero che dava una probabilità di \(3/4\) che si salvassero tutti! Questa era la probabilità ottimale!
Poi mi sono reso conto che questa strategia non esisteva perché ho sbagliato a fare i conti. Ma la strategia ottimale esiste! Nel caso di 2 nanetti è facile e la probabilità ottimale è \(1/2\) wlog il primo nanetto dice il colore opposto a quello che vede e il secondo nanetto dice non lo so. In particolare significa:
-Si salvano con probabilità \(1\) nel caso in cui i cappelli sono (nero,bianco), (bianco, nero).
-Muoiono con probabilità \(1\) nel caso in cui i cappelli sono (nero,nero), (bianco,bianco).
Ergo probabilità \(1/2\).

Mi sono semplicemente corretto dicendo "ahh la probabilità ottimale non è \(3/4\) scusate ho sbagliato! Cambio la domanda che diviene qual è la probabilità ottimale? Invece di dirvi trovare una strategia che li salvi tutti tranne nel caso in cui i cappelli sono (nero,nero) o (bianco, bianco). Ma non ho fatto questo perché ad elencare i casi in cui non si salvano con 7 nanetti diventa lunga"

[axpgn]

Ho capito da 'mo cosa volevi dire (e anche cosa vorresti sapere ma non sono capace di trovarla ), quello che ti contesto da allora è:

"3m0o":Mah... mi sembrava evidente che la domanda era probabilistica ...

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Beh allora siccome sei l'unico a cui ha risposto mi sa che pubblico la soluzione

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Soluzione:

La soluzione generale con \(n\) nani è la seguente: Definiamo un grafo \(G=(V,E)\) a \(2^n \) vertici, dove un vertice \(v=(v_1,\ldots,v_n) \), con \( v_j \in \{ 0,1\} \) per ogni \( 1 \leq j \leq n \), rappresenta una disposizione di cappelli. Diciamo che \(vw \in E \), i.e. il vertice \(v\) è collegato con un arco al vertice \(w\) se e solo se \[ \sum_{ 1 \leq j \leq n} \left| v_j - w_j \right| = 1 \]
o in altre parole se e solo se \(v\) e \(w\) differiscono per una sola coordinata. Ora per un nano, l'osservazione degli altri cappelli equivale a osservare due vertici collegati da un arco, ma non sapere quale dei due vertici corrisponde alla loro disposizione, i.e. al trovarsi su un arco e non sapere in quale dei due vertici andare.


Definizione insieme dominante:
Un insieme dominante \(D\) di raggio \(r\) di un grafo \(G\) è un sottoinsieme dei vertici \( D \subseteq V \) tale che ogni altro vertice di \(V\) è a distanza \(r\) archi da almeno un vertice in \(D\).

Dato \(G\) come descritto inizialmente sia \(g(n) \) la cardinalità minimale di un insieme dominante \(D\) di raggio \(1\). In altre parole dato un vertice in \(D\) possiamo raggiungere qualunque altro vertice di \(V\) percorrendo un solo arco.

Strategia:
I nanetti scelgono \(D\) con cardinalità \(g(n)\) e scommettono che la loro disposizione non sia un vertice di \(D\), i nanetti che osservando due vertici tale che uno si trova in \( V \setminus D \) e l'altro in \(D\) dicono il colore che corrisponde al vertice in \( V \setminus D \), gli altri dicono non lo so.

Spiegazione strategia
Abbiamo infatti in questo modo che se entrambi i vertici osservati da un nano sono in \(D\) allora può fare quello che vuole che muoiono. Se entrambi i vertici osservati da un nano sono in \(V \setminus D \) allora egli dice "non lo so". Se un solo vertice è in \(D\) e l'altro in \(V\setminus D \) allora egli dice il vertice in \(V \setminus D \).
Siccome ogni vertice in cui un nano indovina il proprio colore è adiacente ad un vertice in cui un nano non indovina il proprio colore e per definizione di \(D\) allora è vero che esiste sempre almeno un nano che vede un vertice in \(D\) e un vertice in \( V \setminus D \), infatti se non esistesse avremmo che esiste un vertice in \(V\) che dista 2 da un vertice di \(D\).

Caso 1:
Supponiamo che la disposizione dei cappelli dei nanetti sia un vertice \( v \in V \setminus D \).
Supponiamo che wlog il \(j\)-esimo nanetto vede un vertice in \( D \) e un vertice in \( V \setminus D \), dove i cappelli degli altri sono \(v_1, \ldots, v_{j-1}, v_{j+1}, \ldots , v_n \) e \( u_1= (v_1, \ldots, v_{j-1}, 0,v_{j+1}, \ldots , v_n) \), \( u_2= (v_1, \ldots, v_{j-1}, 1,v_{j+1}, \ldots , v_n) \) sono i vertici osservati al \(j\)-esimo nanetto. Abbiamo che siccome \( v \in V \setminus D \) allora egli dice l'unico vertice tra \(u_1\) e \(u_2\) che sta in \(V \setminus D \) e indovina il proprio colore.
Per quanto riguarda i nanetti che vedono due vertici in \(V \setminus D \) allora essi non capiscono qual è il vertice in \(D\) a cui è collegata la loro disposizioni di cappelli, e quindi diranno "non lo so". Siccome abbiamo supposto che il vertice della disposizione dei cappelli è in \(V \setminus D \) allora nessun nano vedrà due vertici in \(D\). Quindi ricapitolando il \(j\)-esimo nanetto sceglie di dire il vertice che vive in \( V \setminus D \) e indovina, gli altri dicono non lo so e i nanetti sono salvi.

Caso 2:
Supponiamo che la disposizione dei cappelli dei nanetti sia invece un vertice di \( D\), in questo caso tutti i nanetti che non vedono due vertici in \(D\), e ne esiste almeno uno, credono erroneamente di essere il nanetto \(j\)-esimo del caso 1, quindi tutti diranno il colore sbagliato. Siccome c'è un almeno un nano che dice il colore sbagliato i nanetti muoiono indipendentemente dal comportamento dei nani che vedono due vertici in \(D\). Siccome la disposizione dei cappelli si trova in \(D\) nessun nano vedrà due vertici che stanno in \( V \setminus D \).


Probabilità di successo
Il caso 2 accade con probabilità \( \frac{g(n)}{2^n } \) mentre il caso 1 accade con probabilità \( 1- \frac{g(n)}{2^n} \).

La probabilità ottimale è quindi \(p(n) = 1- \frac{g(n)}{2^n} \) e questo segue direttamente per minimalità della cardinalità di \(D\).

Di seguito i valori conosciuti di \(g(n) \) in funzione di \(n\).
\( g(1) = 1, g(2)=g(3)=2, g(4)=4, g(5)=7, g(6)=12, g(7)=16, g(8)=32, g(9)=62 \).

Pertanto \( p(7) = 7/8 \).

Esempio: Con \(n = 3 \) un insieme dominante di cardinalità minimale è dato \(D= \{ (0,0,0);(1,1,1)\} \). Infatti cambiando una componente soltanto puoi ottenere tutte le altre combinazioni.
Supponiamo che la disposizione dei cappelli sia \((v_1,v_2,v_3)=(1,0,0)\) abbiamo che il primo nano osserva i vertici \( (1,0,0) \) oppure \( (0,0,0 ) \) scommette che non è in \(D\) quindi dice che il suo colore è \(1\). Il nano \(v_2 \) invece dice non lo so perché non capisce qual è il vertice in \(D\) a cui sono collegati. Infatti dal suo punto di vista potrebbe essere \( (1,0,0) \) oppure \((1,1,0) \), entrambi i vertici stanno in \(V \setminus D \), infatti nel primo caso sono collegati a \((0,0,0) \) con un arco mentre nel secondo caso a \((1,1,1) \). Lo stesso vale per \(v_3\).
Se la disposizione quindi dei loro cappelli fosse una tra \( \{ (1,0,0), (0,1,0),(0,0,1), (0,1,1),(1,0,1),(1,1,0) \} \) sicuramente un nano indovinerà e gli altri diranno "non lo so".
Se la disposizione invece fosse proprio in \(D = \{ (0,0,0), (1,1,1) \} \), wlog \((0,0,0)\), allora ciascun nano ragiona nel seguente modo: vedo due zeri e quindi scommetto che il mio colore non è in \(D\) e dico \(1\), e quindi diranno tutti \(1\) sbagliando tutti. Questo accade solo in \(2 \) casi su \(8\).