Polinomio tratto da gara asquadre

Polinomi, disuguaglianze, numeri complessi, ...
Rispondi
Avatar utente
lama luka
Messaggi: 326
Iscritto il: 05 feb 2009, 22:21
Località: cittadino del mondo

Polinomio tratto da gara asquadre

Messaggio 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?
Non siamo mica qui a raddrizzare banane col culo !

è Ragionevole!

44 gatti [tex]\equiv 2 \pmod{6}[/tex]

E questo come lo risolvo?-L.Lamanna,G.Grilletti (2009)
Tre anni di quaestio copernicana - C.Càssola, F.M.Antoniali, L.Lamanna (2012)
Cinque anni di Copernicus Math Race - L.Lamanna (2016)

[tex]!n=n! \sum_{k=0}^n \frac{(-1)^k}{k!}[/tex]
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Polinomio tratto da gara asquadre

Messaggio 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...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Avatar utente
lama luka
Messaggi: 326
Iscritto il: 05 feb 2009, 22:21
Località: cittadino del mondo

Re: Polinomio tratto da gara asquadre

Messaggio da lama luka »

Scusa il ritardo nella risposta...! Ti ringrazio tantissimo per il rimando ! :)
Non siamo mica qui a raddrizzare banane col culo !

è Ragionevole!

44 gatti [tex]\equiv 2 \pmod{6}[/tex]

E questo come lo risolvo?-L.Lamanna,G.Grilletti (2009)
Tre anni di quaestio copernicana - C.Càssola, F.M.Antoniali, L.Lamanna (2012)
Cinque anni di Copernicus Math Race - L.Lamanna (2016)

[tex]!n=n! \sum_{k=0}^n \frac{(-1)^k}{k!}[/tex]
lucaboss98
Messaggi: 30
Iscritto il: 02 feb 2014, 19:23
Località: Napoli

Re: Polinomio tratto da gara asquadre

Messaggio 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:
wall98
Messaggi: 167
Iscritto il: 27 mar 2013, 11:23
Località: Roma

Re: Polinomio tratto da gara asquadre

Messaggio 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..
Il problema non è il problema, il problema sei tu.
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Polinomio tratto da gara asquadre

Messaggio 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 \]
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Rispondi