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?
Polinomio tratto da gara asquadre
Polinomio tratto da gara asquadre
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]
è 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]
Re: Polinomio tratto da gara asquadre
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...
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)
Re: Polinomio tratto da gara asquadre
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]
è 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]
-
- Messaggi: 30
- Iscritto il: 02 feb 2014, 19:23
- Località: Napoli
Re: Polinomio tratto da gara asquadre
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..
$ 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..
Re: Polinomio tratto da gara asquadre
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)
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..
$ 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)
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.
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Polinomio tratto da gara asquadre
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 \]
\[ 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