Polinomio bello grosso

[FreddyKruger]

Calcolare le ultime 4 cifre di $p(2019)$, dove $p(x)$ è il polinomio a coefficienti reali di grado 2018 tale che $p(n)=ncdot3^n$ per ogni $n=0,1,2...,2018$

[hydro1]

Immagino che la cosa interessante sia usare la calcolatrice il meno possibile. Ci provo.

Chiaramente bisogna solo calcolare $p(2019)$ modulo $10^4$. Scrivo $2019=2000+19$ e $p=sum a_ix^i$. Siccome $2000^nequiv 0 mod 10^4$ non appena $ngeq 2$, si vede subito che $p(2019)equiv 2000sum a_icdot 19^{i-1}+p(19)=p(19)(2000/19+1)$, e dal momento che per ipotesi $p(19)=19cdot 3^{19}$ ne segue che $p(2019)equiv 2019cdot 3^{19}$. Quindi basta calcolarsi $3^{19}$ modulo $10^4$, che per il teorema cinese del resto è come calcolare $3^{19}$ modulo $16$ e modulo $625$. Modulo $16$ è facile e fa $11$. D'altronde con poca fatica si vede che $3^{10}=-1mod 25$, il che implica che $3^{19}equiv -2cdot 3^9-3^{-1}mod 625$. Calcolare $3^{-1}$ è molto facile perchè $625=3cdot 208+1$, quindi $3^{-1}equiv -208mod 625$. Con un po' più di fatica ma sempre senza calcolatrice si vede che $3^9equiv 308mod 625$ e quindi $3^{19}equiv 217 mod 625$. Adesso bisogna applicare l'algoritmo euclideo alla coppia $(625,16)$, ma anche questo è facile perchè $625=16cdot 39+1$. Ne consegue che $3^{19}equiv 625cdot 11-16cdot 39cdot 217mod 10^4$, operazione che i più coraggiosi possono anche fare a mano scoprendo che $3^{19}equiv 1467mod 10^4$. Ora basta fare $1467cdot 2019equiv 1873$, e il problema è risolto.

[FreddyKruger]

C'è qualcosa che non mi torna, ammetto di aver perso un paio di passaggi per mia ignoranza, ma il risultato non è quello, almeno nella soluzione ufficiale.
Lo metto qui nascosto

$5665$

[axpgn]

@FreddyKruger

Se fai i conti, allora $2019*3^2019$ fa $....1873$
Prova

Cordialmente, Alex

[FreddyKruger]

Signori non so cosa dirvi , è un problema copiato da una gara a squadre di matematica, e la soluzione riportata è quella che ho messo nascosta, dove sta l'errore?
Per esempio non ho capito un cosa, al di là del risultato finale, qual è il polinomio di grado 2019 che rispetta le condizioni del testo? Io personalmente ho avuto difficoltà a trovarlo.

[Super Squirrel]

@axpgn
Non ho ancora approfondito, ma in effetti a prima vista il problema sembra leggermente diverso rispetto a questo:
https://www.matematicamente.it/forum/vi ... 2&t=210848

[FreddyKruger]

Yes, quello era un esercizio che evidentemente era stato tratto da questo problema, anche io ci ho visto una netta somiglianza, ma, ripeto, il polinomio di cui il testo parla mi sembra diverso da quello.

[axpgn]

@Super Squirrel
Mi sembrava di averlo già fatto

@FreddyKruger
Ma il polinomio non devi trovarlo, non è richiesto.
Peraltro a me pare proprio lo stesso.

Cordialmente, Alex

[FreddyKruger]

ok che effettivamente il polinomio non deve essere trovato, ma esiste? e in tal caso quale sarebbe?

[hydro1]

"FreddyKruger":ok che effettivamente il polinomio non deve essere trovato, ma esiste? e in tal caso quale sarebbe?

Che esista è ovvio, stai interpolando 2019 valori distinti quindi esiste unico il polinomio interpolatore di grado 2018.

La mia soluzione sopra è ovviamente sbagliata, visto che mi sono dimenticato un pezzo del coefficiente binomiale nei conti. D'altra parte pensandoci più di 10 secondi è anche ovvio che non sia chiaro per quale motivo $p(2019)$ debba essere intero, visto che $p$ a priori ha coefficienti in $\mathbb Q$.

[axpgn]

"hydro": D'altra parte pensandoci più di 10 secondi è anche ovvio che non sia chiaro per quale motivo $p(2019)$ debba essere intero, visto che $p$ a priori ha coefficienti in $\mathbb Q$.

Beh, ma ... siccome "... per ogni $ n=0,1,2...,2018 $", l'espressione $n\cdot3^n $ è intera e dato che $ p(n)=n\cdot3^n $ allora ne consegue che $p(2019)$ è intero.
No?

Cordialmente, Alex

[axpgn]

E comunque, ripeto che se si fanno i conti, risulta che le ultime quattro cifre di $2019*3^2019$ sono quelle ...

... ovvero $1873$

Cordialmente, Alex

[hydro1]

"axpgn":[quote="hydro"] D'altra parte pensandoci più di 10 secondi è anche ovvio che non sia chiaro per quale motivo $p(2019)$ debba essere intero, visto che $p$ a priori ha coefficienti in $\mathbb Q$.

Beh, ma ... siccome "... per ogni $ n=0,1,2...,2018 $", l'espressione $n\cdot3^n $ è intera e dato che $ p(n)=n\cdot3^n $ allora ne consegue che $p(2019)$ è intero.
[/quote]
Ne consegue perchè? Magari è ovvio eh, ma al momento mi sfugge.

Le ultime 4 cifre di $2019\cdot 3^{2019}$ sono indubbiamente quelle, ma chi ti dice che $p(2019)=2019\cdot 3^{2019}$?

[axpgn]

Scusami ma se scrive che $p(n)$ è uguale a $n*3^n$ per ogni naturale ... e poi, se chiede le ultime quattro cifre, dubito che il numero non sia intero, visto anche come funzionano le gare ... IMHO

[hydro1]

"axpgn":Scusami ma se scrive che $p(n)$ è uguale a $n*3^n$ per ogni naturale ... e poi, se chiede le ultime quattro cifre, dubito che il numero non sia intero, visto anche come funzionano le gare ... IMHO

A me sembra che l'ipotesi sia che $p(n)=n\cdot 3^n$ per ogni $n=0,\ldots,2018$. Anche perchè quale polinomio soddisfa la proprietà che dici tu? Direi nessuno...

[FreddyKruger]

"hydro":
A me sembra che l'ipotesi sia che $ p(n)=n\cdot 3^n $ per ogni $ n=0,\ldots,2018 $. Anche perchè quale polinomio soddisfa la proprietà che dici tu? Direi nessuno...

Era proprio quello il mio dubbio, il polinomio finale NON è $n\cdot 3^n$ perché non soddisfa l'ipotesi

[hydro1]

e soprattutto $ncdot 3^n$ non è un polinomio.

[FreddyKruger]

Infatti, ovviamente non lo è. Se il testo avesse detto "grado 2019" invece che 2018 già era più fattibile. Io avevo ricondotto il testo iniziale al trovare un polinomio con quelle caratteristiche e calcolarlo $mod 10000$ con il valore 2019 al posto della $x$. E' corretto?

[axpgn]

@hydro
Avevo visto qualche puntino in più ...

[FreddyKruger]

Questo problema è della gara a squadre di Cesenatico del 2019, noto che negli ultimi anni il livello di difficoltà è aumentato :O