Gara per il pubblico 2016
Gara per il pubblico 2016
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?
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?
Re: Gara per il pubblico 2016
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.
![Laughing :lol:](./images/smilies/icon_lol.gif)
![Laughing :lol:](./images/smilies/icon_lol.gif)
![Laughing :lol:](./images/smilies/icon_lol.gif)
Re: Gara per il pubblico 2016
Il problema, bello ma difficile secondo me, è stato proposto da Andrea Parma. Aiutino molto piccolo:
Testo nascosto:
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: Gara per il pubblico 2016
Noi con un programmino abbiamo trovato chemr96 ha scritto:ti posso dire che la risposta è 22
Testo nascosto:
Re: Gara per il pubblico 2016
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$.
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
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
Re: Gara per il pubblico 2016
Ehm... È stata la nostra risposta (sbagliata) in garaZar ha scritto:Noi con un programmino abbiamo trovato chemr96 ha scritto:ti posso dire che la risposta è 22
Testo nascosto:
![Laughing :lol:](./images/smilies/icon_lol.gif)
Re: Gara per il pubblico 2016
Eh eh, vedo adesso la soluzione di dario2994, nemmeno con un programmino la si sarebbe potuta trovare...mr96 ha scritto:Ehm... È stata la nostra risposta (sbagliata) in gara
Re: Gara per il pubblico 2016
Ciao, ti chiedo un chiarimento su questo passaggio: esiste una tecnica standard per risolvere questa equazione, oppure si va a tentativi?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$.
Re: Gara per il pubblico 2016
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$.
È 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
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