OliForum Matematico

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.

Premetto che sono decisamente scarso in combinatoria, troppo anche per questo problema che, conoscendo la fonte, non sarebbe dovuto essere poi così difficile. Insicuro della mia soluzione tuttavia ho deciso di provarci. Quindi:
Come vi sembra?

Il problema della tua soluzione è che gli gnomi dipingono a turno, e prima o poi toccherà di nuovo allo stesso gnomo. Questo vuol dire che non puoi usare l'ipotesi induttiva, perché nel caso da cui parti la situazione cicla tra $n$ gnomi, mentre dopo c'è l'$n+1$-esimo gnomo che a priori potrebbe avere amicizie abbastanza losche da sbilanciare lo "redshift" delle case degli altri.
Cioé non ti devi fermare al primo giro.

Hint:

EDIT: sbagliato

EDIT: ho capito l'errore

Ho rivisto la mia soluzione, questa come è?

Indichiamo con $Q_{i}$ l'insieme che racchiude gli amici dello gnomo $i$.
Sia $|R_{i}|=$ numero di case di colore rosso in $Q_{i}$ e $|A_{i}|=$ numero di case di colore azzurro in $Q_{i}$.
Sia $E_{i}$ in $Q_{i}$ la differenza tra le case dello stesso colore di $i$ e quelle non.
Supponiamo che $C_{i}$ sia rossa. Supponiamo che $i$ sia rosso: $E_{i}=|R_{i}|-|A_{i}|$. Alla mossa $n$ $i$ ridipinge la propria casa di azzurro $E_{i}'=|A_{i}|-|R_{i}|$. Se $j$ è rosso in $Q_{j}$, dopo che $i$ ha ridipinto, $|R_{j}'|=|R_{j}|-1$ e $|A_{j}'|=|A_{j}|+1$. \[|R_{j}'|-|A_{j}'|=|R_{j}|-|A_{j}|-2\Rightarrow E_{j}'=E_{j}-2\]
Se $j$ invece ha la casa azzurra $|A_{j}'|=|A_{j}|+1$ e $|R_{j}'|=|R_{j}|-1$.
\[|A_{j}'|-|R_{j}'|=|A_{j}|-|R_{j}|+2\Rightarrow E_{j}'=E_{j}+2\]
\[\sum_{i e amici di i}(E'-E)=2(|A_{i}|-|R_{i}|)-2|R_{i}|+2|A_{i}|=4|A_{i}|-4|R_{i}|> 0\]
Se alla mossa $n$ $i$ non avesse dovuto ridipingere e la sua casa fosse rimasta rossa $E'=E$. Considero $j$ amico di $i$: sia che $j$ abbia la casa blu sia che $j$ abbia la casa rossa $E_{j}'=E_{j}$, da cui $\sum_{Q_{i}}(E'-E)=0$, ovvero rimane costante.
\[0\leq \sum_{i e amici di i}(E'-E)\leq 44\]
\[0\leq\sum_{i=1}^{12}(E_{i}'-E_{i})\leq 12\cdot 44\]
Alla mossa $n+1$ $\sum_{i=1}^{12}(E_{i}'-E_{i})$ può aumentare o rimanere costante.
Considero $U$, numero di coppie di amici con le case di colori differenti: se $\sum_{i=1}^{12}(E_{i}'-E_{i})$ aumenta $U$ diminuisce, se $\sum_{i=1}^{12}(E_{i}'-E_{i})$ rimane invariata, $U$ rimane invariata e quindi nessuno gnomo ridipinge. Se $U$ continua a scendere e non si stabilizza, rimarrà costante, per come è stata definita, a $U=0$, qundi anche $\sum_{i=1}^{12}(E_{i}'-E_{i})$ si stabilizza e quindi anche in questo caso nessuno gnomo dovrà ridipingere.

Grazie per ogni critica e commento

Questa è giusta!

Solo un'osservazione: hai fatto due soluzioni, una valutando la sommatoria e l'altra valutando U. Cioé, non hanno bisogno l'una dell'altra per giustificare la soluzione, vanno bene anche "da sole" (con le osservazioni su come cambiano ad ogni mossa fatte sopra).

Scusa ancora una cosa riguardo questo problema: per giustificare che nonostante qualsiasi decisione presa dagli amici di $i$ la sommatoria aumenta la dimostrazione sarebbe più completa se aggiungessi questa osservazione (che penso sia comunque corretta)?

Alla mossa $n+1$ $\sum_{i=1}^{12}(E_{i}'-E_{i})$ può aumentare o rimanere costante: considero lo gnomo $k$ che viene dopo $i$ e tale che $k$ è amico di $i$. Se $k$ non ridipinge la casa, indipendentemente dal fatto che essa sia rossa o blu, $\sum_{i=1}^{12}(E_{i}'-E_{i})$ non varia. Se $k$ deve ridipingere la casa ho due casi. Se $k$ è rossa e deve ridipingere di azzurro, sia in $Q_{i}$ che in $Q_{k}$, $|A_{i}|$ e $|A_{k}|$ aumentano di una unità, e perciò dopo che ha ridipinto $E_{i}''-E_{i}'=E_{i}'-E_{i}$ e quindi la somma aumenta poichè $|A_{k}'|-|R_{k}'|>|R_{k}|-|A_{k}|$. Se invece $k$ deve ridipingere la casa di rosso, in $Q_{i}$ avrò $E_{i}''=E_{i}'-2$ e in $Q_{k}$ $E_{k}'=E_{k}+2$ e quindi $E_{i}''+E_{k}'=E_{i}'+E_{k}$, e quindi la somma rimane costante.

Grazie ancora.

Si, l'osservazione (dovrebbe) essere giusta

Per la sua necessità, beh, in generale più chiarifichi la soluzione meglio è.