Pagina 1 di 1

54. Mossa dopo mossa

Inviato: 21 giu 2015, 19:25
da cip999
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

Inviato: 04 ago 2015, 10:05
da simone256
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

Re: 54. Mossa dopo mossa

Inviato: 04 ago 2015, 12:04
da AlexThirty
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?

Re: 54. Mossa dopo mossa

Inviato: 04 ago 2015, 12:25
da simone256
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:

Re: 54. Mossa dopo mossa

Inviato: 12 ago 2015, 16:13
da cip999
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$ :)

Re: 54. Mossa dopo mossa

Inviato: 12 ago 2015, 18:37
da simone256
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 $

Re: 54. Mossa dopo mossa

Inviato: 13 ago 2015, 10:32
da cip999
Perfetto, vai pure :)