I dodici gnomi

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Nadal21
Messaggi: 164
Iscritto il: 12 mar 2015, 15:30

I dodici gnomi

Messaggio da Nadal21 » 06 apr 2016, 15:41

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
Messaggi: 143
Iscritto il: 10 giu 2015, 21:38

Re: I dodici gnomi

Messaggio da alegh » 09 apr 2016, 00:58

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?

Avatar utente
karlosson_sul_tetto
Messaggi: 1436
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: I dodici gnomi

Messaggio da karlosson_sul_tetto » 09 apr 2016, 17:28

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
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

alegh
Messaggi: 143
Iscritto il: 10 giu 2015, 21:38

Re: I dodici gnomi

Messaggio da alegh » 09 apr 2016, 18:29

EDIT: sbagliato
Ultima modifica di alegh il 11 apr 2016, 20:01, modificato 1 volta in totale.

alegh
Messaggi: 143
Iscritto il: 10 giu 2015, 21:38

Re: I dodici gnomi

Messaggio da alegh » 09 apr 2016, 18:42

EDIT: ho capito l'errore
Ultima modifica di alegh il 11 apr 2016, 20:02, modificato 1 volta in totale.

alegh
Messaggi: 143
Iscritto il: 10 giu 2015, 21:38

Re: I dodici gnomi

Messaggio da alegh » 11 apr 2016, 19:57

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

Avatar utente
karlosson_sul_tetto
Messaggi: 1436
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: I dodici gnomi

Messaggio da karlosson_sul_tetto » 11 apr 2016, 21:13

Questa è giusta! :D

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).
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

alegh
Messaggi: 143
Iscritto il: 10 giu 2015, 21:38

Re: I dodici gnomi

Messaggio da alegh » 11 apr 2016, 23:10

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.

Avatar utente
karlosson_sul_tetto
Messaggi: 1436
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: I dodici gnomi

Messaggio da karlosson_sul_tetto » 12 apr 2016, 18:03

Si, l'osservazione (dovrebbe) essere giusta :)

Per la sua necessità, beh, in generale più chiarifichi la soluzione meglio è.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

Rispondi