Gara per il pubblico 2016

La competizione di matematica più spettacolare che ci sia!
Rispondi
Zar
Messaggi: 14
Iscritto il: 10 mag 2016, 22:55

Gara per il pubblico 2016

Messaggio da 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] l'insieme di tutti i numeri che si possono ottenere sommando le cifre di un multiplo di 2015 (diverso da zero), e [math] il minimo di [math]. Quante cifre ha il più piccolo multiplo di 2015 la cui somma delle cifre fa esattamente [math]?

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
Messaggi: 151
Iscritto il: 05 gen 2015, 01:07

Re: Gara per il pubblico 2016

Messaggio da mr96 »

Questo (bellissimo) quesito ci ha fatto perdere la gara del pubblico: terzi con -40 su questo problema che era il nostro jolly :lol: 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 :lol: :lol: Mi aggrego anche io quindi sperando ci sia una soluzione elegante senza troppa teoria dietro.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Gara per il pubblico 2016

Messaggio da 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$? ...
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Zar
Messaggi: 14
Iscritto il: 10 mag 2016, 22:55

Re: Gara per il pubblico 2016

Messaggio da Zar »

mr96 ha scritto:ti posso dire che la risposta è 22
Noi con un programmino abbiamo trovato che
Testo nascosto:
[math], quindi [math] e la risposta dovrebbe essere 9. Si riesce a trovare un numero tale che [math] sia minore di 5?
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: Gara per il pubblico 2016

Messaggio da 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$.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
mr96
Messaggi: 151
Iscritto il: 05 gen 2015, 01:07

Re: Gara per il pubblico 2016

Messaggio da mr96 »

Zar ha scritto:
mr96 ha scritto:ti posso dire che la risposta è 22
Noi con un programmino abbiamo trovato che
Testo nascosto:
[math], quindi [math] e la risposta dovrebbe essere 9. Si riesce a trovare un numero tale che [math] sia minore di 5?
Ehm... È stata la nostra risposta (sbagliata) in gara :lol:
Zar
Messaggi: 14
Iscritto il: 10 mag 2016, 22:55

Re: Gara per il pubblico 2016

Messaggio da Zar »

mr96 ha scritto:Ehm... È stata la nostra risposta (sbagliata) in gara :lol:
Eh eh, vedo adesso la soluzione di dario2994, nemmeno con un programmino la si sarebbe potuta trovare...
Zar
Messaggi: 14
Iscritto il: 10 mag 2016, 22:55

Re: Gara per il pubblico 2016

Messaggio da Zar »

dario2994 ha scritto: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
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: Gara per il pubblico 2016

Messaggio da 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$.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Zar
Messaggi: 14
Iscritto il: 10 mag 2016, 22:55

Re: Gara per il pubblico 2016

Messaggio da Zar »

Ok, grazie.
Rispondi