Gnomi e cappelli

[axpgn]

In una grotta buia vivono molti gnomi.
Ogni gnomo ha in testa un cappello rosso oppure azzurro.
Ognuno vede il cappello di tutti gli altri ma non il proprio, dunque non sa di quale colore sia il suo cappello.
Un giorno gli gnomi sono costretti ad uscire dalla grotta uno dopo l'altro e devono disporsi in modo che da una parte ci siano i cappelli rossi e dall'altra gli azzurri.
Essi però non possono scambiarsi nemmeno una parola né farsi cenni o cose del genere.
Non possono assolutamente comunicare tra loro!
Come possono fare?


Cordialmente, Alex

[axpgn]

"Help us"

[Studente Anonimo]

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.

[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