Generalizzando vecchi cortona
Generalizzando vecchi cortona
Ci sono $ n $ persone intorno ad un tavolo rotondo, una possiede $ 5n $ monete, tutte le altre $ 0 $. Ad ogni turno una persona che ha più di due monete può dare una moneta ad ognuno dei suoi due vicini. Determinare per quali $ n $ si può arrivare alla configurazione in cui tutti hanno $ 5 $ monete in un numero finito di turni.
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
Mi sembra di capire che funzioni solo con n dispari, perché se n è pari, procedendo simmetricamente (unica procedura che mi pare possibile) alla fine si rimarrebbe con un'unica persona senza monete e, visto che le si devono dare monete da 2 parti, non ne avrà mai 5, non essendo 5 divisibile per 2. Utilizzando un procedimento simmetrico con un numero dispari invece non si incontrano difficoltà. Determinare questi numeri non implica una dimostrazione o qualcosa di simile, vero Boll?
ciao ciao
ciao ciao
"Sei la Barbara della situazione!" (Tap)
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Il problema originale era determinare se con n = 22 si possa ottenere una configurazione in cui tutti hanno 5 monete in un numero finito di turni
Si può risolvere come segue: coloro alternativamente di bianco e di rosso le persone.
Sia B la somma delle monete possedute dai bianchi.
Sia N la somma delle monete possedute dai rossa.
La mossa possibile è:
aumentare di due B e calare di due N o viceversa.
La parità di B e di N è quindi invariante rispetto alla mossa.
La situazione iniziale è: B $ \equiv $ N $ \equiv $ 0 (mod 2) ma alla fine dovrei avere B $ \equiv $ N $ \equiv $ 1 mod 2 che è assurdo.
Si può risolvere come segue: coloro alternativamente di bianco e di rosso le persone.
Sia B la somma delle monete possedute dai bianchi.
Sia N la somma delle monete possedute dai rossa.
La mossa possibile è:
aumentare di due B e calare di due N o viceversa.
La parità di B e di N è quindi invariante rispetto alla mossa.
La situazione iniziale è: B $ \equiv $ N $ \equiv $ 0 (mod 2) ma alla fine dovrei avere B $ \equiv $ N $ \equiv $ 1 mod 2 che è assurdo.
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
ok all'inizio (saranno un paio di settimane) non volevo proprio postare pechè è troppo brutta come soluzione..poi però ci ho ripensato solo per fare arrabbiare Boll 
Per il caso generale purtroppo non ho trovato nessun invariante carino (mi pare che Boll l'abbia trovato però..) e ho un po' scannonato.
Si trova facilmente a mano una strategia che mostri che con n dispari si può ottenere una configurazione in cui tutti hanno 5 monete in un numero finito di turni.
Claim: se n è pari non posso ottenere una configurazione in cui tutti hanno 5 monete in un numero finito di turni.
pongo n=2j
Sia chiamata a_1 la persona che inizialmente ha 5n = 10j monete.
Siano chiamate $ a_2,a_3,a_4,...,a_n $ le 2j-1 persone successive secondo il verso orario.
Sia m_i il numero di mosse effettuato nella i-esima posizione per ottenere la situazione finale.
ottengo il sistema:
1) $ -2m_2+m_3=5-m_1 $
2) $ m_2-2m_3+m_4=5 $
...
2j-1) $ m_{2j-1}-2m_{2j}=5-m_1 $
tra 2j-1 relazioni.
Posso risolvere il sistema in funzione di m_1 se il determinante della matrice 1 è diverso da 0:
matrice 1:
$ \left [ \begin{array}{ccccccc} -2 & 1 & 0 & 0 & ... & 0 & 0 \\ 1 & -2 & 1 & 0 & ... & 0 & 0 \\ 0 & 1 & -2 & 1 & ... & 0 & 0 \\ ... & ... & ... & ... & ... & ... & ... & \\ 0 & 0 & 0 & 0 & ... & 1 & -2 \end{array} \right ] $
Step 1: il determinante è diverso da 0:
Chiamo $ D_n $ il determinante della matrice “bella” con n colonne e n righe.
Ottengo facilmente (considerando la definizione di determinante e osservando che se tolgo la prima fila e la prima colonna alla matrice bella con n colonne ottengo la matrice bella con n-1 colonne.. ) la relazione ricorsiva:
$ D_n = -2D_{n-1} $ – $ D_{n-2} $ e anche
$ D_1= -2 $
$ D_2 = 3 $
$ D_3 = -4 $
Congetturo che la funzione $ f(n) = |D_n| $ sia crescente.
Lo dimostro per induzione:
HP: $ |D_{n-1}| > |D_{n-2}| $
TH: $ |D_n| > |D_{n-1}| $
$ |D_{n-1}| > |D_{n-2}| \rightarrow $
$ 2|D_{n-1}| - |D_{n-2| > |D_{n-1}| \rightarrow $
$ |D_n| $ = $ |2D_{n-1}+D_{n-2}| $ $ \ge 2 |D_{n-1}| - |D_{n-2| $ > $ |D_{n-1}| $
quindi essendo f(n) crescente e essendo f(1) > 0 il determinante di una matrice bella non potrà mai essere nullo.
Step 2: $ m_{2j}=m_2 $
Sia
A = $ \left | \begin{array}{ccccccc} 5-m_1 & 1 & 0 & 0 & ... & 0 & 0 \\ 5 & -2 & 1 & 0 & ... & 0 & 0 \\ 5 & 1 & -2 & 1 & ... & 0 & 0 \\ ... & ... & ... & ... & ... & ... & ... & \\ 5-m_1 & 0 & 0 & 0 & ... & 1 & -2 \end{array} \right | $
B = $ \left | \begin{array}{ccccccc} -2 & 1 & 0 & 0 & ... & 0 & 5-m_1 \\ 1 & -2 & 1 & 0 & ... & 0 & 5 \\ 0 & 1 & -2 & 1 & ... & 0 & 5 \\ ... & ... & ... & ... & ... & ... & ... & \\ 0 & 0 & 0 & 0 & ... & 1 & 5-m_1 \end{array} \right | $
Per Cramer:
$ x_2= \frac{A}{D_{2j}} $
$ x_{2j}= \frac{B}{D_{2j}} $
ponendo i coefficenti di $ m_2 $ nell'ultima colonna, quelli di $ m_3 $ nella penultima e così via fino a quelli di $ m_{2j} $ nella prima e ordinando le righe partendo dai coefficenti della relazione 2j-1 fino alla 1 ottango anche che (sempre per Cramer):
$ x_2= \frac{B}{D_{2j}} $
e quindi B=A e $ x_2=x_{2j} $.
Step 3: conclusione.
Inoltre il sistema iniziale diventa:
1) $ -2m_2+m_3=5-m_1 $
2) $ m_2-2m_3+m_4=5 $
...
2j-1) $ m_{2j-1}-2m_{2j}=5-m_1 $ = $ m_{2j-1}-2m_{2}=5-m_1 $
da cui confrontando la 1 e la 2j-1 ottengo $ m_{2j-1}=m_{3} $
sempre per confronti successivi ottengo:
$ m_{2j-2}=m_{4} $
..
$ m_{j}=m_{j+2} $
e la relazione j-1 diventa:
$ m_J+m_{j+2}-2m_{j+1} = 2m_j-2m_{j+1}=5 $
che è assurdo modulo 2.
Brutta no?
PS a meno di ciofeche mi è stata riferita una soluzione di poche righe..a voi stà trovarla..
Buona domenica, Simone.
Per il caso generale purtroppo non ho trovato nessun invariante carino (mi pare che Boll l'abbia trovato però..) e ho un po' scannonato.
Si trova facilmente a mano una strategia che mostri che con n dispari si può ottenere una configurazione in cui tutti hanno 5 monete in un numero finito di turni.
Claim: se n è pari non posso ottenere una configurazione in cui tutti hanno 5 monete in un numero finito di turni.
pongo n=2j
Sia chiamata a_1 la persona che inizialmente ha 5n = 10j monete.
Siano chiamate $ a_2,a_3,a_4,...,a_n $ le 2j-1 persone successive secondo il verso orario.
Sia m_i il numero di mosse effettuato nella i-esima posizione per ottenere la situazione finale.
ottengo il sistema:
1) $ -2m_2+m_3=5-m_1 $
2) $ m_2-2m_3+m_4=5 $
...
2j-1) $ m_{2j-1}-2m_{2j}=5-m_1 $
tra 2j-1 relazioni.
Posso risolvere il sistema in funzione di m_1 se il determinante della matrice 1 è diverso da 0:
matrice 1:
$ \left [ \begin{array}{ccccccc} -2 & 1 & 0 & 0 & ... & 0 & 0 \\ 1 & -2 & 1 & 0 & ... & 0 & 0 \\ 0 & 1 & -2 & 1 & ... & 0 & 0 \\ ... & ... & ... & ... & ... & ... & ... & \\ 0 & 0 & 0 & 0 & ... & 1 & -2 \end{array} \right ] $
Step 1: il determinante è diverso da 0:
Chiamo $ D_n $ il determinante della matrice “bella” con n colonne e n righe.
Ottengo facilmente (considerando la definizione di determinante e osservando che se tolgo la prima fila e la prima colonna alla matrice bella con n colonne ottengo la matrice bella con n-1 colonne.. ) la relazione ricorsiva:
$ D_n = -2D_{n-1} $ – $ D_{n-2} $ e anche
$ D_1= -2 $
$ D_2 = 3 $
$ D_3 = -4 $
Congetturo che la funzione $ f(n) = |D_n| $ sia crescente.
Lo dimostro per induzione:
HP: $ |D_{n-1}| > |D_{n-2}| $
TH: $ |D_n| > |D_{n-1}| $
$ |D_{n-1}| > |D_{n-2}| \rightarrow $
$ 2|D_{n-1}| - |D_{n-2| > |D_{n-1}| \rightarrow $
$ |D_n| $ = $ |2D_{n-1}+D_{n-2}| $ $ \ge 2 |D_{n-1}| - |D_{n-2| $ > $ |D_{n-1}| $
quindi essendo f(n) crescente e essendo f(1) > 0 il determinante di una matrice bella non potrà mai essere nullo.
Step 2: $ m_{2j}=m_2 $
Sia
A = $ \left | \begin{array}{ccccccc} 5-m_1 & 1 & 0 & 0 & ... & 0 & 0 \\ 5 & -2 & 1 & 0 & ... & 0 & 0 \\ 5 & 1 & -2 & 1 & ... & 0 & 0 \\ ... & ... & ... & ... & ... & ... & ... & \\ 5-m_1 & 0 & 0 & 0 & ... & 1 & -2 \end{array} \right | $
B = $ \left | \begin{array}{ccccccc} -2 & 1 & 0 & 0 & ... & 0 & 5-m_1 \\ 1 & -2 & 1 & 0 & ... & 0 & 5 \\ 0 & 1 & -2 & 1 & ... & 0 & 5 \\ ... & ... & ... & ... & ... & ... & ... & \\ 0 & 0 & 0 & 0 & ... & 1 & 5-m_1 \end{array} \right | $
Per Cramer:
$ x_2= \frac{A}{D_{2j}} $
$ x_{2j}= \frac{B}{D_{2j}} $
ponendo i coefficenti di $ m_2 $ nell'ultima colonna, quelli di $ m_3 $ nella penultima e così via fino a quelli di $ m_{2j} $ nella prima e ordinando le righe partendo dai coefficenti della relazione 2j-1 fino alla 1 ottango anche che (sempre per Cramer):
$ x_2= \frac{B}{D_{2j}} $
e quindi B=A e $ x_2=x_{2j} $.
Step 3: conclusione.
Inoltre il sistema iniziale diventa:
1) $ -2m_2+m_3=5-m_1 $
2) $ m_2-2m_3+m_4=5 $
...
2j-1) $ m_{2j-1}-2m_{2j}=5-m_1 $ = $ m_{2j-1}-2m_{2}=5-m_1 $
da cui confrontando la 1 e la 2j-1 ottengo $ m_{2j-1}=m_{3} $
sempre per confronti successivi ottengo:
$ m_{2j-2}=m_{4} $
..
$ m_{j}=m_{j+2} $
e la relazione j-1 diventa:
$ m_J+m_{j+2}-2m_{j+1} = 2m_j-2m_{j+1}=5 $
che è assurdo modulo 2.
Brutta no?
PS a meno di ciofeche mi è stata riferita una soluzione di poche righe..a voi stà trovarla..
Buona domenica, Simone.
hmm... non ho controllato per bene tutto, ma a una prima lettura mi viene un piccolo dubbio. Hai dimostrato che il determinante della matrice è diverso da zero; questo ti permette di concludere che il sistema ha soluzione nei razionali, ma poi sembri usare le $ m_i $ come se fossero intere.
Puoi chiarirmi bene la questione di cosa è razionale e cosa è intero nella soluzione?
Grazie,
Puoi chiarirmi bene la questione di cosa è razionale e cosa è intero nella soluzione?
Grazie,
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Prima dimostro che ho soluzione (nei razionali).fph ha scritto:hmm... non ho controllato per bene tutto, ma a una prima lettura mi viene un piccolo dubbio. Hai dimostrato che il determinante della matrice è diverso da zero; questo ti permette di concludere che il sistema ha soluzione nei razionali, ma poi sembri usare le $ m_i $ come se fossero intere.
Puoi chiarirmi bene la questione di cosa è razionale e cosa è intero nella soluzione?
Grazie,
Poi qualsiasi $ m_i $ è per definizione intero poichè è il numero di mosse effettuato nella i-esima posizione per ottenere la situazione finale.
Ma ciò porta ad un'assurdo modulo 2 quindi la situazione finale non è raggiungibile per n pari.
Spero sia più chiaro così.
Domattina parto per una settimana di gita in Grecia e non riuscirò a dare spiegazioni o correggere eventuali s*****ate per un po' (la soluzione l'ho scritta un di fretta..per esempio non ho detto che la matrice 1 è la matrice "bella" e non ho spiegato bene come ottenere la ricorsione anche se è facilmente dimostrabile..)
Buona settimana a tutti
