Pagina 1 di 1

Polinomio tratto da gara asquadre

Inviato: 04 feb 2014, 23:22
da lama luka
Salve a tutti ! Vi propongo un problema incontrato giorni fa in una simulazione a squadre che ci ha causato (e causa tutt'ora) non pochi dubbi esistenziali (il problema)..

Riassumendo: trovare tutti i possibili valori di p(1), quando p è un polinomio a coefficienti interi tale che p(0)=0, $ 0 \leq p(1) < 10^5 $ e per cui esiste un intero a tale che p(a)=2013. Quanti sono i possibili valori?

Re: Polinomio tratto da gara asquadre

Inviato: 05 feb 2014, 09:56
da Drago96
Uhm, qua c'è un problema simile, ma è molto più stringente...
Per questo, dopo aver detto $ a\mid2013 $, penso che occorra fare tutti i casi e non penso che sia molto agevole...

Re: Polinomio tratto da gara asquadre

Inviato: 17 feb 2014, 12:15
da lama luka
Scusa il ritardo nella risposta...! Ti ringrazio tantissimo per il rimando ! :)

Re: Polinomio tratto da gara asquadre

Inviato: 28 feb 2014, 13:02
da lucaboss98
Dato che $ p(0) = 0 $ ho che
$ p(x) = x \cdot q(x) $
Ne segue che
$ x | p(x) $ per ogni $ x $ appartenente a $ Z $
Allora $ a | 2013 = 3 \cdot 11 \cdot 61 $
se $ a=1 $ ho $ p(1) = 2013 $ e un polinomio che prova che è possibile è $ p(x) = x^{2013} + x^{2012} + . . . + x^2 + x $
Ma se $ a=3 , a=11, a=33, a=61, a=183, a=671, a=2013, a=-1, a=-3, a=-11, a=-33, a=-61, a=-183, a=-671, a=-2013 $ non saprei farlo, potreste spiegarmelo?
Potrei provare con un $ a-1 | p(a) - p(1) = 2013 - p(1) $ , ma non so se è la strada giusta.. :roll:

Re: Polinomio tratto da gara asquadre

Inviato: 01 mar 2014, 13:05
da wall98
Credo di essere vicino alla soluzione ma non riesco a concludere, sono arrivato a:

$ P(x)= a_nx^n+..a_2x^2+a_1x $

$ (x-a) (\frac{P(x)}{x}+\sum^{n-1}_{k=0} (x^k \cdot \frac{a^k \cdot a_k + a^{k-1}\cdot a_{k-1}...+a^2 \cdot a_2+a \cdot a_1 -2013}{a^{k+1}})=P(x)-2013 $

Pongo l'attenzione su $ \sum^{n-1}_{k=0} (x^k \cdot \frac{a^k \cdot a_k + a^{k-1}\cdot a_{k-1}...+a^2 \cdot a_2+a \cdot a_1 -2013}{-a^{k+1}}) $

Ogni termine della sommatoria deve essere intero (cioè ogni $ \displaystyle \frac{a^i \cdot a_i + a^{i-1}\cdot a_{i-1}...+a^2 \cdot a_2+a \cdot a_1 -2013}{-a^{i+1}} $)

Perchè essi sono i coefficienti del polinomio $ \displaystyle \frac{P(x)-2013}{x-a}-\frac{P(x)}{x} $, che ha coefficienti interi (se questo ragionamento è utile poi scrivo i conti).

Ora visto che ogni $ a_i $ e $ a $ sono fissati all'inizio, vorrei trovare per quali valori di essi quei termini sono sempre interi, penso che a parte $ a=1,-1 $ non ce ne siano altri, perchè mi pare abbastanza "difficile" una cosa del genere...


E solo ora mi viene in mente che questo problema è una trollata assurda (a meno che non mi stia trollando da solo) :D

Infatti supponiamo per comodità che ogni coefficiente è +1, sia $ N_p $ il numero di x con l' esponente pari e sia $ N_d $ il numero di x con l'esponente dispari, ponendo $ a=-1 $ si ha che $ N_p-N_d=2013 $, quindi $ P(1)=N_p+N_d=2013+2 N_d $ puo essere ogni valore dispari maggiore uguale a 2013

Ora notiamo che possiamo aggiungere $ m $ coppie del tipo del tipo $ -x^{2r+1}-x^{2s} $ e notiamo come il polinomio in -1 vale sempre lo stesso valore, mentre in 1 invece cala di 2 per ogni coppia, dunque anche ogni dispari minore o uguale a 2013

Oppure per dimostrare che il valore puo sempre aumentare a coppie, aggiungiamo $ +x^{2r}+x^{2s+1} $ e notiamo come in -1 rimane invariato, mentre aumenta a coppie quando è 1.

$ P(1) $ quindi puo valere tutti i dispari.

Non puo valere un numero pari, supponiamo ora il polinomi in forma aperta, cioè del tipo $ a_nx^n+a_{n-1}x^{n-1}+..+a_0 $, cioè dove i coefficienti non sono piu pari a 1.

Vale che $ (x-a) q(x)=P(x)-2013 \longrightarrow P(1)=(1-a) q(1) +2013 $, se $ p(1) $ è pari $ a $ deve essere pari, ma se cosi fosse, non potrebbe essere $ P(a)=2013 $ che è dispari dato che $ P(0)=0 $.

Dunque la risposta è "tutti i dispari".

Qualcuno ha idee su come continuare la mia dimostrazione o comunque dimostrare il caso generale, cioè:

trovare tutti i possibili valori di p(x), quando p è un polinomio a coefficienti interi tale che p(0)=0, $ 0≤p(1)<10^5 $ e per cui esiste un intero a tale che p(a)=n. Quanti sono i possibili valori? che alla fine basta togliere 2013 è il mio tentativo di dimostrazione in generale dovrebbe valere ancora..

Re: Polinomio tratto da gara asquadre

Inviato: 02 mar 2014, 16:14
da Gottinger95
Diciamo che con le tecniche "normali", tipo che se \(p(a) = b\) allora \(p(x) = b+ (x-a) q(x)\) e poi si continua su \(q(x)\) se uno ha altri valori, si arriva facilmente a (se tipo volete scrivo come ci si arriva passo passo):
\[ p(x) = \frac{nx}{a}+ x(x-a) q(x) \]
per qualche polinomio \(q(x)\) e per \(a \mid n\). Perciò \(p(1) = \dfrac{n}{a} - (a-1)q(1) \), ossia
1. \(p(1) \equiv \dfrac{n}{a} \pmod{a-1}\), che si riduce a \(p(1) \equiv n \pmod{a-1} \), per \(a\) diverso da 1
2. \(p(1) = n\) per \(a=1\)
Adesso, se \(n \equiv 3 \pmod{6}\) (ossia \(n\) dispari e \(3 \mid n\)), allora con \(a=3\) abbiamo \(p(1) \equiv 1 \pmod{2} \). Notate che potendo scegliere \(q(x)\) come ci pare, possiamo effettivamente trovare un polinomio che abbia come \(p(1\) \) un dispari che ci pare.
Perciò @wall98: se \(n\) non è congruo a 3 modulo 6, o non possiamo porre \(a=3\) (quindi non possiamo ottenere una condizione mod 2), oppure la risposta è proprio al contrario, ossia i pari funzionano e i dispari boh. Anzi,se \(2 \mid n\) possiamo porre \(a=2\) e otteniamo che vanno bene proprio tutti i numeri! :)

Per il problema generale invece, la questione è trovare i numeri che sono congrui a \(n\) modulo qualcosa che +1 divide \(n\) e che sono più piccoli di un certo \(M\). Se uno vuole proprio scrivere una formula si può scrivere, ma è abbastanza una forzatura ed è solo un virtuosismo formale (lo farò lo stesso perchè è divertente). Detti:
1. \(A_{\delta} = \{1, \ldots, \delta\}\), dove \(\delta\) è il numero di divisori di \(n\);
2. \( d(I_k) \) prodotto \( (d_{i_1} -1 ) \cdot \ldots \cdot (d_{i_k} -1)\), dove \(I_k= (i_1,\ldots, i_k)\)e i \(d_i\) sono divisori di \(n\);
3. \(r(I_k)\) il resto di \(n\) diviso per \(D(I_k)\);
abbiamo che il numero cercato è, per il principio di inclusione-esclusione:
\[ \sum_{I_k \subseteq A_{\delta} } (-1)^{k+1} \left \lfloor \frac{M-r(I_k) }{d(I_k)} \right \rfloor \]