I dodici gnomi

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

I dodici gnomi

Messaggioda Nadal01 » 06/04/2016, 14:47

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.
Nadal01
 
Messaggi: 68
Iscritto il: 16/01/2015, 17:12

Re: I dodici gnomi

Messaggioda Rho33 » 06/04/2016, 19:14

Carino e semplice , da dove viene? :D

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) .
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: I dodici gnomi

Messaggioda Nadal01 » 07/04/2016, 14:47

Dalla sezione "Combinatoria 2" dell'eserciziario del senior 2014 che ho scaricato dall'Oliforum. :D ;)
Nadal01
 
Messaggi: 68
Iscritto il: 16/01/2015, 17:12


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti