I dodici gnomi

[Nadal21]

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.

[alegh]

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:

Testo nascosto:

$Q$= insieme degli amici di uno gnomo.
$|Q|$= cardinalità dell'insieme degli amici di uno gnomo.
Ogni gruppo di amici viene rappresentato come un grafo di cui gli gnomi sono i vertici e viene indicato come $G$. Sia $nG$ il numero di grafi considerati. Ovviamente $nG$= numero di gnomi considerati
Ogni grafo $G$ ha $|Q|+1$ vertici e considerando tutti i grafi vi sono $|Q|+1$ vertici etichettati nello stesso modo per ogni gnomo.
- Passo base: $2G$. Ho $G_{A}$ e $G_{B}$: $A$ è dello stesso colore di $B$.
- Ipotesi induttiva: suppongo che la tesi sia vera per $nG$, ovvero $n$ gnomi.
- Passo induttivo: ho $n+1$ gnomi e $(n+1)G$.
Nomino $i$ l'$n+1-esimo$ elemento. Suppongo sia rosso poiché in $Q_{i}$ la maggioranza è rossa. $i$ si trova in $|Q_{i}|$ grafi oltre a $G_{i}$. Considero il caso in un cui vi sia un grafo $G_{j}$ in cui $j$ sia colorato d'azzurro e $i$ faccia variare la maggioranza, ovvero aggiungendo $i$, $\lfloor\frac{|Q_{j}|+1}{2}\rfloor$ sia colorata di rosso. $j$ cambia colore in tutti i grafi cui appartiene, aggiungendo quindi un elemento rosso.
Possono quindi cambiare le maggioranza nei grafi.
Con l'ipotesi induttiva avevamo supposto che la tesi fosse verificata con $n$ gnomi.
Sia $|R|$ il numero di case rosse e sia $|A|$ il numero di case azzurre. $|R|$ può o aumentare o rimanere invariato. $|A|$ può diminuire o rimanere invariato. Ho due casi:
-$|A|=0$, la maggioranza varia in tutti i grafi e la configurazione finale presenta solo case rosse.
-esiste almento un grafo in cui la maggioranza non varia o che non è interessato dai cambiamenti negli altri grafi. Questi gnomi avranno la casa dipinta di azzurro come la maggioranza dei loro amici e non dovranno ridipingere.

Come vi sembra?

[karlosson_sul_tetto]

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:

Testo nascosto:

Cerca di farlo in modo più combinatorico, magari con invarianti

[alegh]

EDIT: sbagliato

[alegh]

EDIT: ho capito l'errore

[alegh]

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

[karlosson_sul_tetto]

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).

[alegh]

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.

[karlosson_sul_tetto]

Si, l'osservazione (dovrebbe) essere giusta

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