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.
