I dodici gnomi

[Nadal01]

In una valle incantata vivono 12 gnomi, i cui nomi coincidono con i mesi dell'anno. Ognuno di essi abita in una casetta dipinta di azzurro o di rosso.
Nel mese di Gennaio, lo gnomo Gennaio va a trovare tutti i suoi amici. Se la maggioranza stretta di essi ha la casa di un dato colore diverso da quello della propria casetta, egli adegua il colore della propria casetta a tale maggioranza.
Nel mese di Febbraio, è lo gnomo Febbraio a fare tale ragionamento.
Questa procedura si ripete ogni mese. Supposto che nella propria lista amici ogni gnomo non includa se stesso e che l'amicizia è simmetrica, mostrare che da un certo momento in poi nessuno dovrà ridipingere la propria casa.

[Rho33]

Carino e semplice , da dove viene?

Testo nascosto:

Considero un generico gnomo $A$ e definisco:

$b= \text{numero di amici con la casa dello stesso colore}$

$c= \text{numero di amici con la casa di colore diverso}$

Sia inoltre $N_i$ il numero di coppie di amici aventi le case di colori diversi dopo $i$ mosse ( stavolta tra tutti gli gnomi ovviamente)

Supponiamo che $A$ cambi il colore della sua casa alla $i+1- \text{esima}$ mossa, allora in quell'istante $c>b$. Chiaramente $N_{i+1}= N_i+b-c < N_i $ . Questa quantità ad ogni mossa decresce, ma chiaramente non può avvenire $N_j<0$ dopo $j$ mosse perchè essa conta il numero di amicizie, allora da un certo punto in poi sarà $N_j=0$ ( se vuoi giustificarlo meglio è per il Principio della Discesa infinita) .

[Nadal01]

Dalla sezione "Combinatoria 2" dell'eserciziario del senior 2014 che ho scaricato dall'Oliforum.