Gara per il pubblico 2016

[Zar]

Ciao, non ho trovato altri thread di discussione sulla gara per il pubblico di Cesenatico, spero di essere nel posto giusto.

Mi piacerebbe analizzare il quesito 8, che dice questo: sia [math]S l'insieme di tutti i numeri che si possono ottenere sommando le cifre di un multiplo di 2015 (diverso da zero), e [math]n il minimo di [math]S. Quante cifre ha il più piccolo multiplo di 2015 la cui somma delle cifre fa esattamente [math]n?

Io ho trovato un risultato che dovrebbe essere giusto, ma che è stato calcolato col computer. Mi piacerebbe arrivare a una dimostrazione del fatto che quello è proprio il risultato corretto (e mi piacerebbe anche capire come si possa arrivare al risultato "a mano"). Penso si debba lavorare sulle congruenze, ma mi pianto.

Qualcuno ha qualche idea da condividere?

[mr96]

Questo (bellissimo) quesito ci ha fatto perdere la gara del pubblico: terzi con -40 su questo problema che era il nostro jolly ti posso dire che la risposta è 22, e che a mano non saprei come farlo. Quello che ho fatto io per provarci è: considero $a_1=1$, $a_2=11$, $a_3=111$ e così via, prima di $a_{2016}$ troverò di sicuro $1\leq m,n \leq 2016$ tali che $a_m \equiv a_n \pmod{2015}$, e allora $2015 \mid |a_m-a_n|$ che sarà formato da qualche (si spera pochi) $1$ all'inizio e tanti $0$ dopo, ma non ho avuto idee furbe per trovare questi due valori. Invece di bruteforce siamo arrivati a un numero di 9 cifre con somma 5, che evidentemente non era giusto Mi aggrego anche io quindi sperando ci sia una soluzione elegante senza troppa teoria dietro.

[fph]

Il problema, bello ma difficile secondo me, è stato proposto da Andrea Parma. Aiutino molto piccolo:

Testo nascosto:

Cominciate a pensare a quanto può valere questo minimo $n$. Per esempio, si riesce a fare con $n=1$? Con $n=2$? ...

[Zar]

ti posso dire che la risposta è 22

Noi con un programmino abbiamo trovato che

Testo nascosto:

[math]2015\cdot 50134 = 101020010, quindi [math]n=5 e la risposta dovrebbe essere 9. Si riesce a trovare un numero tale che [math]n sia minore di 5?

[dario2994]

Posto una soluzione rapida a cui, gli interessati, possono aggiungere gli opportuni dettagli.

Denoto con $k$ il numero che realizza la somma delle cifre $n$. Vale $2015=5\cdot 13\cdot 31$. Inoltre l'ordine di $10$ modulo $13$ e $31$ è rispettivamente $6$ e $15$.

Innanzitutto non si realizza $n=1$.
Si realizza $n=2$? Se fosse allora $k=10^a+10^b$ e quindi si avrebbe che $10^c\equiv -1\pmod{31}$ ma questo è impossibile.
Si realizza $n=3$? Se fosse allora ci sono due possibili forme per $k$.
Se $k$ è della forma $2\cdot 10^a+10^b$ allora si deve avere $10^c\equiv -2 \pmod{13}$ ma questo è impossibile.
Allora $k$ è della forma $10^a+10^b+10^c$ e, chiedendo che sia minimo ed imponendo la congruenza modulo $5$ e $13$, si trova che deve essere della forma $10^{6x+3}+10^{6y+5}+10$.
A questo punto resta da aggiustare la congruenza modulo $31$. Si impone che $7\cdot 2^x+18\cdot 2^y\equiv -1\pmod{31}$ e si trova che la soluzione è data da $x=3$ ed $y=1$.
Quindi $k=10^{21}+10^{11}+10$.

Le cose più lunghe da fare a mano (con il silenzio intorno si fanno in 5 minuti al più) sono calcolare l'ordine di $10$ modulo $31$ e trovare che alla fine $x=3$ e $y=1$.

[mr96]

ti posso dire che la risposta è 22

Noi con un programmino abbiamo trovato che

Testo nascosto:

[math]2015\cdot 50134 = 101020010, quindi [math]n=5 e la risposta dovrebbe essere 9. Si riesce a trovare un numero tale che [math]n sia minore di 5?

Ehm... È stata la nostra risposta (sbagliata) in gara

[Zar]

Ehm... È stata la nostra risposta (sbagliata) in gara

Eh eh, vedo adesso la soluzione di dario2994, nemmeno con un programmino la si sarebbe potuta trovare...

[Zar]

A questo punto resta da aggiustare la congruenza modulo $31$. Si impone che $7\cdot 2^x+18\cdot 2^y\equiv -1\pmod{31}$ e si trova che la soluzione è data da $x=3$ ed $y=1$.

Ciao, ti chiedo un chiarimento su questo passaggio: esiste una tecnica standard per risolvere questa equazione, oppure si va a tentativi?

[dario2994]

Vogliamo risolvere $7\cdot 2^x+18\cdot 2^y\equiv -1\pmod{31}$.
È facile convincersi che le potenze di $2$ modulo $31$ sono $1, 2, 4, 8, 16$.
Ora le moltiplichiamo per $7$ e $18$:
$7, 14, 28, 25, 19$
$18, 5, 10, 20, 9$
e ci resta solo vedere se la somma di uno della prima riga con uno della seconda fa $30$. (non può fare $61$ perché è troppo grande). È facile convincersi che l'unica possibilità è $25+5$ che coincide con $x = 3, y = 1$.

[Zar]

Ok, grazie.