Testo nascosto, fai click qui per vederlo
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\).
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\).
)