Finale Cesenatico 2007: problema 22

[Gabuntu94]

Ciao!

Stavo sfogliando i testi delle passate edizioni di Cesenatico. Mi sono imbattuto in questo del 2007:

Numeruto e la sua squadra sono all’inseguimento dei rapitori di Sekante. I nostri mateninja avanzano cauti, gli inseguiti hanno disseminato il percorso di trappole. All’improvviso, Numeruto incappa in un tranello.
Sia $ p(x) = \left(\frac{x^4+x^2+1}{3}\right)^{2007} $. Se $ p(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_{8028} x^{8028} $, l’unico modo per sottrarsi alla trappola è calcolare $ a_1 + a_4 + a_7 + \ldots + a_{3k+1} + \ldots + a_{8026} $. Dare come risposta la somma di numeratore e denominatore del risultato ridotto ai minimi termini.

Qual è l'idea di fondo per questo problema? Ho provato (quasi) di tutto! Comprese radici dell'unità


Grazie in anticipo!

[fph]

Qual è l'idea di fondo per questo problema? Ho provato (quasi) di tutto! Comprese radici dell'unità

Ritenta con le radici dell'unità.
Quanto fa $ p(\zeta_3) $? E $ p(\zeta_3^2) $? E $ p(\zeta_3^3) $? Come si scrivono in termini degli $ a_i $?

(Filed under: discrete Fourier transform)

[Gabuntu94]

Ritenta con le radici dell'unità.
Quanto fa $ p(\zeta_3) $? E $ p(\zeta_3^2) $? E $ p(\zeta_3^3) $? Come si scrivono in termini degli $ a_i $?

Dunque...
Chiamo $ \omega=\zeta_3 $
$ p(\omega) = a_0+\omega a_1+\omega^2 a_2 + a_3 + \omega a_4 + \omega^2 a_5 + a_6 + \ldots + a_{8028}=0 $
$ p(\omega^2) = a_0+\omega^2 a_1+\omega a_2 + a_3 + \omega^2 a_4 + \omega a_5 + a_6 + \ldots + a_{8028}=0 $
$ p(\omega^3) = a_0+a_1+ a_2 + a_3 + a_4 + a_5 + a_6 + \ldots + a_{8028}=1 $

(Filed under: discrete Fourier transform)

Cosa vuol dire? Nel senso... Ho provato a cercarla, ma non ho capito molto bene!

Avevo pensato anche io alle radici terze... Mi sento sempre di più in colpa...

[Tibor Gallai]

Somma membro a membro, e puf!

Presumo che si tratti di una gara a squadre, non l'individuale..??
P.S. Mi rispondo da solo: sì. -.-

[Gabuntu94]

Ma a me sommando membro a membro risulta $ 3(a_0 +a_3+a_6+...) $

Dove sbaglio?


--- edit
Ok forse ci sono... basta moltiplicare per $ \omega $ nella prima e per $ \omega^2 $ nella seconda!

[Tibor Gallai]

Ah sì, ricordavo male il testo. Come hai detto tu si sistema (in realtà al contrario di come dici...).

[Gabuntu94]

Oh sì ho sbagliato a scriverli... Sarà meglio che vada a dormire: per oggi ho già combinato abbastanza guai!

Grazie mille!

[Tibor Gallai]

L'importante è andare a dormire a problema risolto, così si dorme meglio...

[fph]

Bene, problema risolto. Più in generale, hai trovato tre equazioni nelle tre incognite $ A=\sum a_{3k} $, $ B=\sum a_{3k+1} $, $ C=\sum a_{3k+2} $, puoi metterle a sistema e puf. Lo stesso trucco funziona per qualunque polinomio (o anche per "polinomi infiniti" tipo le serie di Taylor di funzioni analitiche, per chi le conosce).

(Filed under: discrete Fourier transform)

Cosa vuol dire? Nel senso... Ho provato a cercarla, ma non ho capito molto bene!

Uhm, sorry, hai ragione sono stato un po' criptico io. È un argomento di matematica "avanzata" (~universitaria) che porta un po' più avanti tecniche come quella che hai visto per risolvere questo problema e le usa in problemi più avanzati. Non era un commento diretto a te, ma una noticina per chi la conosce già "ehi, guardate, in questo problema c'è una versione elementare della DFT".

(by the way, il problema era una mia proposta. A me piaceva, spero anche a voi).

[Gabuntu94]

Bene, problema risolto. Più in generale, hai trovato tre equazioni nelle tre incognite $ A=\sum a_{3k} $, $ B=\sum a_{3k+1} $, $ C=\sum a_{3k+2} $, puoi metterle a sistema e puf. Lo stesso trucco funziona per qualunque polinomio (o anche per "polinomi infiniti" tipo le serie di Taylor di funzioni analitiche, per chi le conosce).

(Filed under: discrete Fourier transform)

Cosa vuol dire? Nel senso... Ho provato a cercarla, ma non ho capito molto bene!

Uhm, sorry, hai ragione sono stato un po' criptico io. È un argomento di matematica "avanzata" (~universitaria) che porta un po' più avanti tecniche come quella che hai visto per risolvere questo problema e le usa in problemi più avanzati. Non era un commento diretto a te, ma una noticina per chi la conosce già "ehi, guardate, in questo problema c'è una versione elementare della DFT".

Oh.. Capisco...

(by the way, il problema era una mia proposta. A me piaceva, spero anche a voi).

Certo! Non era niente male

[karl]

Il risultato si può ottenere ,se non ho fatto sbagli,con le seguenti considerazioni ultra-elementari:

1) Le potenze ( intere ) di $ \displaystyle x^4+x^2+1 $ sono polinomi
in cui i coefficienti estremi e quelli equidistanti dagli estremi sono uguali.
Come accade nel triangolo di Pascal-Tartaglia

2) La somma dei coefficienti delle potenze del tipo $ x^{3k+1} $ è esattamente
la metà della somma dei restanti coefficienti.E poiché la somma
totale di tutti i coefficienti è$ p(1) =1 $,ne segue che la somma richiesta
è $ \frac{1}{3} $

Per la dimostrazione si può usare l'induzione e speriamo non sia solo un ...puf !!!
[Questo fatto del "puf" mi sembra solo un modo mascherato per dire
"vedete quanto sono bravo io e quanto siete ignoranti voi ! "]

[fph]

Notate anche che il $ x^4+x^2+1 $ era lì per gentilezza: il problema avrebbe funzionato con qualunque altro polinomio, ma sarebbe stato molto più difficile farsi venire in mente le radici terze dell'unità

[karl]

Questo della "gentilezza " è la perfetta conferma di quanto ho prima scritto
sulla "bravura" propria e sulla "inconsistenza " degli altri.Grazie ,dunque !!!

[Tibor Gallai]

[Questo fatto del "puf" mi sembra solo un modo mascherato per dire
"vedete quanto sono bravo io e quanto siete ignoranti voi ! "]

Mi sa di no...
http://www.urbandictionary.com/define.php?term=puf
http://www.urbandictionary.com/define.php?term=poof
http://www.urbandictionary.com/define.php?term=pouf

[karl]

Mancano solo il " pif,paf e pef " e stiamo al completo !