54. Mossa dopo mossa
54. Mossa dopo mossa
Siano dati $n$ interi. Una mossa consiste nel selezionare $m$ di questi interi ($m \le n$) e aggiungere $1$ a ciascuno di essi. Per quali $n$ ed $m$ è sempre possibile raggiungere una configurazione in cui gli $n$ interi sono tutti uguali?
Re: 54. Mossa dopo mossa
Dai ci provo io che è bloccata da un bel po'...
Siano i numeri scritti sulla lavagna gli $ a_i $ con $ 1 \leq i \leq n $ e definiamo $ R=n a_{max} - \sum a_i $ dove $ a_max $ è il più grande tra gli $ a_i $ (o uno dei più grandi).
Vinciamo se e solo se:
$ \mbox{gcd}(m,n) | R $
Il se si dimostra perchè per bezout abbiamo un $ k $ e un $ j $ naturali tali che $ jm-kn=R $, quindi $ jm=R+kn $. Quindi effettuando la mossa $ j $ volte possiamo diciamo "livellare" tutti gli $ a_i $ al valore $ a_{max} $ e alzare tutti i valori di $ k $ ottenendo tutti valori uguali.
Il solo se si vede perchè per vincere ovviamente deve esistere un $ k $ tale che $ m | kn + R $ (per raggiungere il livellamento detto prima); quindi $ \mbox{gcd}(m,n) | R + kn $ e infine $ \mbox{gcd}(m,n) | R $.
Spero funzi
Siano i numeri scritti sulla lavagna gli $ a_i $ con $ 1 \leq i \leq n $ e definiamo $ R=n a_{max} - \sum a_i $ dove $ a_max $ è il più grande tra gli $ a_i $ (o uno dei più grandi).
Vinciamo se e solo se:
$ \mbox{gcd}(m,n) | R $
Il se si dimostra perchè per bezout abbiamo un $ k $ e un $ j $ naturali tali che $ jm-kn=R $, quindi $ jm=R+kn $. Quindi effettuando la mossa $ j $ volte possiamo diciamo "livellare" tutti gli $ a_i $ al valore $ a_{max} $ e alzare tutti i valori di $ k $ ottenendo tutti valori uguali.
Il solo se si vede perchè per vincere ovviamente deve esistere un $ k $ tale che $ m | kn + R $ (per raggiungere il livellamento detto prima); quindi $ \mbox{gcd}(m,n) | R + kn $ e infine $ \mbox{gcd}(m,n) | R $.
Spero funzi
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
-
AlexThirty
- Messaggi: 217
- Iscritto il: 20 giu 2015, 20:58
Re: 54. Mossa dopo mossa
Bomba la Prima parte mi sembra molto buona ma la seconda non lho capita molto...
Più che altro non capisco perché passi da $ m|kn+R $ a $ gcd (m,n)|kn+R $.
E sufficiente dire che il gcd divide quella cosa per dire che anche tutto $ m $ lo divide?
Più che altro non capisco perché passi da $ m|kn+R $ a $ gcd (m,n)|kn+R $.
E sufficiente dire che il gcd divide quella cosa per dire che anche tutto $ m $ lo divide?
Un bresciano esportato nel cremonese
-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.
-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.
Re: 54. Mossa dopo mossa
Se non sto facendo bordello, è il contrario!
visto che $ \mbox{gcd}(m,n) | m $ e che per necessità per vincere $ m | R + kn $ per un qualche $ k $; allora di sicuro $ \mbox{gcd}(m,n) | R + kn $.
Ma poichè $ \mbox{gcd}(m,n) | n $ riscrivo meglio come $ \mbox{gcd}(m,n) | R $. Questo è necessario per vincere; il fatto che è sufficiente (in teoria ) è dimostrato sopra! 
visto che $ \mbox{gcd}(m,n) | m $ e che per necessità per vincere $ m | R + kn $ per un qualche $ k $; allora di sicuro $ \mbox{gcd}(m,n) | R + kn $.
Ma poichè $ \mbox{gcd}(m,n) | n $ riscrivo meglio come $ \mbox{gcd}(m,n) | R $. Questo è necessario per vincere; il fatto che è sufficiente (in teoria
) è dimostrato sopra! $ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
Re: 54. Mossa dopo mossa
Potrei anche darla per buona, tanto l'idea c'è. Però il testo chiedeva un criterio in base ai soli $m$ ed $n$ per determinare se è sempre possibile (cioè qualunque siano gli interi di partenza) renderli tutti uguali. Ma arrivato a questo punto basta davvero un attimo per concludere.
PS: $\gcd(m, n) \mid R$ equivale a $\displaystyle \gcd(m, n) \mid \sum a_i$
PS: $\gcd(m, n) \mid R$ equivale a $\displaystyle \gcd(m, n) \mid \sum a_i$
Re: 54. Mossa dopo mossa
Ops! Hai proprio ragione! Ho interpretato male il testo 
Quindi sperando di non dire una stupidata abbiam bisogno di
$ \mbox{gcd}(m,n)=1 $
Quindi sperando di non dire una stupidata abbiam bisogno di
$ \mbox{gcd}(m,n)=1 $
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
Re: 54. Mossa dopo mossa
Perfetto, vai pure