54. Mossa dopo mossa

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
cip999
Messaggi: 148
Iscritto il: 26 nov 2013, 14:44

54. Mossa dopo mossa

Messaggio da cip999 » 21 giu 2015, 19:25

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?
- E cosa c'è di peggio del suicidio?
- La vita.

Avatar utente
simone256
Messaggi: 452
Iscritto il: 07 mag 2012, 16:10
Località: Crema

Re: 54. Mossa dopo mossa

Messaggio da simone256 » 04 ago 2015, 10:05

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 :P
$ \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

AlexThirty
Messaggi: 217
Iscritto il: 20 giu 2015, 20:58

Re: 54. Mossa dopo mossa

Messaggio da AlexThirty » 04 ago 2015, 12:04

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?
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.

Avatar utente
simone256
Messaggi: 452
Iscritto il: 07 mag 2012, 16:10
Località: Crema

Re: 54. Mossa dopo mossa

Messaggio da simone256 » 04 ago 2015, 12:25

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 :P ) è dimostrato sopra! :wink:
$ \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

cip999
Messaggi: 148
Iscritto il: 26 nov 2013, 14:44

Re: 54. Mossa dopo mossa

Messaggio da cip999 » 12 ago 2015, 16:13

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$ :)
- E cosa c'è di peggio del suicidio?
- La vita.

Avatar utente
simone256
Messaggi: 452
Iscritto il: 07 mag 2012, 16:10
Località: Crema

Re: 54. Mossa dopo mossa

Messaggio da simone256 » 12 ago 2015, 18:37

Ops! Hai proprio ragione! Ho interpretato male il testo :roll:

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

cip999
Messaggi: 148
Iscritto il: 26 nov 2013, 14:44

Re: 54. Mossa dopo mossa

Messaggio da cip999 » 13 ago 2015, 10:32

Perfetto, vai pure :)
- E cosa c'è di peggio del suicidio?
- La vita.

Rispondi