Pagina 1 di 2

Polinomio da cesenatico

Inviato: 14 lug 2018, 01:12
da Maionsss
Sia $ p(x) =( \frac{x^4+x^2+1}{3})^{2007} = a_0+a_1x^1+.....+a_{8028}x^{8028} $ Determinare $ a_1+ a_7+....a_{3k+1}+...a_{8026} $.
Dare come risposta la somma tra numeratore e denominatore del risultato ridotto ai minimi termini.
Testo nascosto:
qualcuno che mi spiega come va risolta questa tipologia di esercizi in cui dato un polinomio si chiede la somma di particolari coefficienti...
Testo nascosto:
servono le radice n-esime dell'unità?
Testo nascosto:
il risultato è $ 4 $

Re: Polinomio da cesenatico

Inviato: 14 lug 2018, 11:22
da Fenu
Testo nascosto:
Molto spesso esercizi come questo si risolvono utilizzando le radici $n$-esime dell'unità. Ti lascio una formula da dimostrare e $2$ esercizi da risolvere che utilizzano questa strategia, se hai bisogno di hint chiedili.
1)Dimostrare che la somma dei coefficienti dei termini di grado divisibile per $k$ di $p(x)$ corrisponde a
$$\frac{p(1)+p(\omega)+p(\omega^2)+...+p(\omega^{k-1})}{k}$$
dove $\omega, \omega^2, ...$ sono le radici $k$-esime complesse dell'unità.
Testo nascosto:
Prova a capire cosa succede in $p(\omega^k)$ e in che modo sommiamo i coefficienti.
Esercizi di prova:
-Calcolare $\sum \binom{n}{3k}$, $\sum \binom{n}{3k+1}$.
-Calcolare la probabilità che, lanciati $n$ dadi, la somma dei punteggi ottenuti sia un multiplo di $7$.
Testo nascosto:
Prova ad utilizzare le funzioni generatrici, se non trovi altro modo
Tutto ciò era per rispondere al tuo primo "hide".
Per quanto riguarda il problema che hai proposto, puoi risolverlo in questo modo, oppure notando che in generale, i modi di formare $3k+1$ con quegli esponenti non sono così tanto imprevedibili.

Re: Polinomio da cesenatico

Inviato: 14 lug 2018, 11:29
da bananamaths
@Fenu sai qualche dispensa dove potrei imparare le radice n_esime del unità(cioè so cosa sono non ho ancora capito come si usano) e sai dove potrei leggere anche qualcosa sulle funzioni generatrici? Ringrazio in anticipo

Re: Polinomio da cesenatico

Inviato: 14 lug 2018, 11:52
da Fenu
bananamaths ha scritto:
14 lug 2018, 11:29
@Fenu sai qualche dispensa dove potrei imparare le radice n_esime del unità(cioè so cosa sono non ho ancora capito come si usano) e sai dove potrei leggere anche qualcosa sulle funzioni generatrici? Ringrazio in anticipo
Per quanto riguarda le funzioni generatrici, le ho spesso trovate leggendo l'$Engel$ e il $Larson$, anche se forse in quest'ultimo la tipologia di problemi affrontati è diversa da quella olimpica attuale.
Ti lascio questo link: http://imomath.com/index.php?options=355 .
Per quanto riguarda le radici $n$-esime, ci sono talmente tanti posti che non saprei quale consigliarti :D ... guarda qualche video del senior basic e dovresti essere OK per le cose principali.

Re: Polinomio da cesenatico

Inviato: 14 lug 2018, 11:55
da bananamaths
Ti ringrazzio :D :D

Re: Polinomio da cesenatico

Inviato: 15 lug 2018, 02:15
da Maionsss
Ti ringrazio da subito per i tuoi suggerimenti :D
Per prima cosa provo a dimostrare la formula sperando di non aver detto qualche scemenza :?
Testo nascosto:
Sia $ p(x) =a_nx_n+ a_{n-1}x^{n-1}+....+a_1x+a_0 $ e siano $ \omega, \omega^2,....\omega^{k-1} $ radici $ k $-esime complesse dell'unità. Consideriamo ora la somma $ p(1)+p(\omega)+p(\omega^2)+.....+p(\omega^{k-1}) $, immaginiamo di scrivere i polinomi per esteso
$ p(1)= a_n+a_{n-1}+....+a_0 $
$ p(\omega) = a_n\omega^n+a_{n-1}\omega^{n-1}+...+a_0 $
$ \vdots $
$ p(\omega^{k-1})=a_n(\omega^{k-1})^n+a_{n-1}(\omega^{k-1})^{n-1}+.....+a_0 $ e di sommare i monomi simili tenendo conto di due cose:
$ 1) (\omega^i )^j =1 \forall i=1,....,k-1 e \forall j: k|j $
$ 2) \displaystyle \sum_{i=1}^{k-1}\omega^i +1=0 $.
Andando a fare la somma dei polinomi ci accorgiamo che i coefficienti dei termini di grado divisibile per $ k $ saranno tutti uguali a $ k $, mentre i restanti coefficienti saranno nulli in quanto, tramite oppurtuni raccoglimenti, riusciamo sempre a ricondurci all'osservazione $ 2) $. La somma finale sarà dunque $ k\displaystyle \sum_{j : k|j} a_j $ che, divisa per $ k $ ci dà appunto la somma richiesta.
Testo nascosto:
sperando che la dimostrazione precedente sia giusta vorrei chiederti delle hint per gli esercizi visto che non ho ben capito come sfruttare queste osservazioni per risolvere gli esercizi :roll:

Re: Polinomio da cesenatico

Inviato: 16 lug 2018, 10:46
da Fenu
Maionsss ha scritto:
15 lug 2018, 02:15
Ti ringrazio da subito per i tuoi suggerimenti :D
Per prima cosa provo a dimostrare la formula sperando di non aver detto qualche scemenza :?
Testo nascosto:
Sia $ p(x) =a_nx_n+ a_{n-1}x^{n-1}+....+a_1x+a_0 $ e siano $ \omega, \omega^2,....\omega^{k-1} $ radici $ k $-esime complesse dell'unità. Consideriamo ora la somma $ p(1)+p(\omega)+p(\omega^2)+.....+p(\omega^{k-1}) $, immaginiamo di scrivere i polinomi per esteso
$ p(1)= a_n+a_{n-1}+....+a_0 $
$ p(\omega) = a_n\omega^n+a_{n-1}\omega^{n-1}+...+a_0 $
$ \vdots $
$ p(\omega^{k-1})=a_n(\omega^{k-1})^n+a_{n-1}(\omega^{k-1})^{n-1}+.....+a_0 $ e di sommare i monomi simili tenendo conto di due cose:
$ 1) (\omega^i )^j =1 \forall i=1,....,k-1 e \forall j: k|j $
$ 2) \displaystyle \sum_{i=1}^{k-1}\omega^i +1=0 $.
Andando a fare la somma dei polinomi ci accorgiamo che i coefficienti dei termini di grado divisibile per $ k $ saranno tutti uguali a $ k $, mentre i restanti coefficienti saranno nulli in quanto, tramite oppurtuni raccoglimenti, riusciamo sempre a ricondurci all'osservazione $ 2) $. La somma finale sarà dunque $ k\displaystyle \sum_{j : k|j} a_j $ che, divisa per $ k $ ci dà appunto la somma richiesta.
Testo nascosto:
sperando che la dimostrazione precedente sia giusta vorrei chiederti delle hint per gli esercizi visto che non ho ben capito come sfruttare queste osservazioni per risolvere gli esercizi :roll:
La dimostrazione è corretta.
Per quanto riguarda i problemi..
1) Considera il polinomio $p(x)=(1+x)^n$. Usando l'espansione del binomio di Newton ricavi che i coefficienti dei termini di grado divisibile per $3$ sono tutti e soli i binomi della forma $\binom{n}{3k}$.. quindi ora usi il filtro delle radici che hai dimostrato ed hai finito. Per la seconda somma, prova ad osservare dove compaiono i binomiali della forma $\binom{n}{3k+1}$ tra i coefficienti del polinomio $x^2(1+x)^n$ (magari compaiono proprio nei termini di grado divisibile per $3$), e concludi con il filtro delle radici.
2)Funzione generatrice per il lancio di n dadi: $q(x)=(x+x^2+x^3+x^4+x^5+x^6)^n$. Cosa significa questo? Significa che, lanciando $n$ dadi e sommando il loro valore, esistono esattamente $[x^k]$ "casi" dei $6^n$ possibili che ci danno come somma $k$ (dove con $[x^k]$ intendo il coefficiente di $x^k$ in $q(x)$). Ora se noi vogliamo che la somma sia divisibile per $7$ e ci interessa la probabilità, troviamo tutti i casi favorevoli (filtro delle radici) e dividiamo per $q(1)$ (ovvero la somma dei coefficienti, nonchè tutti i casi possibili, $6^n$) ed è finito. Ti invito a risolverli per prendere familiarità con i piccoli calcoli che si presentano.

Re: Polinomio da cesenatico

Inviato: 16 lug 2018, 13:22
da Drago96
Fenu ha scritto:
16 lug 2018, 10:46
2)Funzione generatrice per il lancio di n dadi: $q(x)=(x+x^2+x^3+x^4+x^5+x^6)^n$. Cosa significa questo? Significa che, lanciando $n$ dadi e sommando il loro valore, esistono esattamente $[x^k]$ "casi" dei $6^n$ possibili che ci danno come somma $k$ (dove con $[x^k]$ intendo il coefficiente di $x^k$ in $q(x)$). Ora se noi vogliamo che la somma sia divisibile per $7$ e ci interessa la probabilità, troviamo tutti i casi favorevoli (filtro delle radici) e dividiamo per $q(1)$ (ovvero la somma dei coefficienti, nonchè tutti i casi possibili, $6^n$) ed è finito. Ti invito a risolverli per prendere familiarità con i piccoli calcoli che si presentano.
Piccola osservazione : invece di dividere a mano per $6^n$, fai la vera funzione generatrice del lancio di un dado, che è semplicemente $f(x)=\frac 1 6 \left( x+x^2+\dots+x^6\right)$ ed è già normalizzata nel senso che $f(1)=1$. Poi la elevi alla $n$ se vuoi $n$ lanci indipendenti.
In generale ad ogni probabilità discreta si può associare la sua generatrice $\sum_{n\ge0} p(n)x^n$ che ha molte proprietà interessanti (esempio: per trovare il valore atteso basta valutare in $1$ la derivata)

P.S: anche il problema originario si può vedere come generatrice di una probabilità, e quindi direi che il risultato non può essere $4$...
P.P.S: il posto dove imparare le generatrici è abbastanza questo

Re: Polinomio da cesenatico

Inviato: 16 lug 2018, 14:07
da bananamaths
Ma le generatrici sono utili anche nelle dimostrazioni o servono sopratutto per problemi di combinatoria a conteggi?

Re: Polinomio da cesenatico

Inviato: 20 lug 2018, 18:51
da Maionsss
@Drago96 infatti il risultato finale del problema è la somma tra numeratore e denominatore della frazione ridotta ai minimi termini

Re: Polinomio da cesenatico

Inviato: 20 lug 2018, 19:24
da Maionsss
@Fenu ho risolto gli esercizi che mi avevi proposto,scusa se ci ho messo tanto ma in questi giorni non ho avuto proprio tempo.
Testo nascosto:
$1)$ Per la prima sommatoria si arriva alla formula $\frac{2^n+(1+\omega)^n + (1+\omega^2)^n}{3}$ con $\omega,\omega^2$ radici terze dell' unità; Per la seconda sommatoria ugualmente consideriamo $\omega,\omega^2$ radici terze dell' unità e stavolta chiamiamo $p(x)=x^2(x+1)^n$ : si arriva dunque alla formula $\frac{2^n+ p(\omega) + p(\omega^2)}{3}$
$2)$ Per i dadi invece consideriamo le radici settime dell’unità $\omega,....,\omega^6$ e la funzione generatrice $q(x)= (\frac{x+....+x^6}{6})^n$ del lancio di $n$ dadi : la probabilità è data da $\frac{q(1)+....q(\omega^6)}{7}$
Fatti gli esercizi vorrei sapere come poter applicare questa nuova tecnica del filtro delle radici al problema di partenza...

Re: Polinomio da cesenatico

Inviato: 20 lug 2018, 21:05
da Fenu
Diciamo che le risposte sono quelle ma... quando parlavo di "prendere familiarità" con i conti, intendevo letteralmente imparare a semplificare e lavorare con quelle espressioni.. Entrambi i problemi hanno risposte "chiuse", senza polinomi o somme. Prova a semplificare.
Esempio:
Testo nascosto:
Dato che \omega è una radice cubica, nel primo problema magari si nota che $(1+\omega)$ equivale a $-\omega^2$ e magari riusciamo a semplificare qualcosa..
Fammi sapere se hai bisogno di altro aiuto.
Una volta che impari a semplificare le espressioni, il problema da te proposto dovrebbe risultare istantaneo.

Re: Polinomio da cesenatico

Inviato: 20 lug 2018, 21:21
da Maionsss
Ah scusa credevo che per " prendere familiarità" intendessi dimostrare perché da quelle espressioni si arrivava a quelle formule. Comunque per quanto riguarda la semplificazioni, appena ho un po' di tempo per studiare meglio le radici dell'unità e le loro proprietà, ci provo. Se ho bisogno di aiuto scrivo, grazie ancora.

Re: Polinomio da cesenatico

Inviato: 25 lug 2018, 20:23
da Maionsss
@Fenu provo il problema sui dadi
Testo nascosto:
Sia $n$ il numero di dadi lanciati. La probabilità richiesta è forse $\frac{6^{n-1}+(-1)^n}{7\cdot{6^{n-1}}}$?

Re: Polinomio da cesenatico

Inviato: 26 lug 2018, 10:09
da Fenu
Giusto :D.