Pagina 1 di 1

longlisted 1969

Inviato: 30 mag 2015, 22:23
da luca95
Dato un polinomio $ f(x) $ a coefficienti interi il cui valore è divisibile per 3 per tre interi $ k,k+1,k+2 $ (cioè $ 3\vert f(k),3\vert f(k+1),3\vert f(k+2) $), dimostrare che $ 3\vert f(m) $ per ogni intero $ m $.

Re: longlisted 1969

Inviato: 31 mag 2015, 22:20
da Enigmatico
Spero di non aver travisato il problema...
Testo nascosto:
Se uno tra $k$, $k+1$ e $k+2$ è multiplo di $3$ non possono esserlo anche gli altri due. Pertanto, se $3|f(k+1)\land 3|f(k+2)\land3|f(k)$, $f(k+1)=3a_{n} (k+1)^{n} + ... + 3a_{0}=3(a_{n}(k+1)^{n}+...+a_{0})$ e lo stesso ragionamento, a meno di opportune sostituzioni, vale per $f(k+2)$ e $f(k)$.
Dunque, $3|f(x) \Rightarrow 3|f(m)$ per ogni $m$.

Re: longlisted 1969

Inviato: 31 mag 2015, 22:47
da matpro98
Spero di non sbagliare, ma chi ti dice che l'unica possibilità è che ogni coefficiente sia multiplo di 3? L'unica certezza è che lo è il termine noto... o no?

Re: longlisted 1969

Inviato: 31 mag 2015, 23:28
da luca95
Matpro ha ragione, non è detto che ogni coefficiente sia multiplo di 3, ad esempio $ n^3+2n+3 $ è divisibile per 3 per ogni $ n $ naturale

Re: longlisted 1969

Inviato: 01 giu 2015, 14:17
da Enigmatico
Avete ragione, l'ho sparata grossa... Nel pomeriggio provo a correggermi!

Re: longlisted 1969

Inviato: 01 giu 2015, 15:18
da 6frusciante9
Probabilmente mi sbaglio ma :

WLOG $ 3|k $ dunque $ 3|f(k)=a_nk^n+ \ldots +a_0 $ ma allora $ 3|a_0 $
$ 3|f(k+1) \equiv_3 a_n+a_{n-1}+ \ldots a_1 $ dunque $ \sum_{1}^{n}a_i \equiv_3 0 $
Analogamente ricaviamo che $ \sum_{i=1}^{n} 2^ia_i \equiv _3 0 $
Quindi a seconda del fatto che un certo intero $ m $ sia congruo ad $ 1,2,0 $ modulo $ 3 $
useremo una delle tre precedenti deduzioni per mostrare che $ f(m) \equiv_3 0 $

Re: longlisted 1969

Inviato: 01 giu 2015, 17:11
da luca95
No è giusto, infatti basta rendersi conto che per qualunque polinomio $ P(k)\equiv P(k+p) \pmod {p} $, quello che conta per la divisibilità non è $ k $ ma solo il suo resto nella divisione per $ p $

Re: longlisted 1969

Inviato: 01 giu 2015, 17:40
da 6frusciante9
Si in effetti credo si posa generalizzare abbastanza agevolmente ...

Re: longlisted 1969

Inviato: 02 giu 2015, 09:30
da santilli
Domanda xD
Io so che ogni polinomio è esprimibile come :
$ (x-a_0) (x-a_1)... $

Posso quindi dire che se sostituisco ad $ x $ i valori $ k,k+1,k+2 $ e ogni volta risulta divisibile per tre allora ogni volta vi è una parentesi tra le tante che diventa multipla di tre , altrimenti il risultato non potrebbe essere divisibile per tre se esso non apparisse tra i suoi fattori.
Supponendo quindi per comodità che $ k \equiv 0 (mod 3) $ e di conseguenza $ (k+1) \equiv 1 (mod 3) $ e $ (k+2) \equiv 2 (mod 3) $ , posso dire che qualsiasi numero congruo a $ 0 \mod \ 3 $ farebbe risultare un multiplo di tre nel prodotto esattamente nel posto della stessa parentesi dove k aveva fatto questa cosa. (stessa cosa con un numero $ 1\ mod\ 3 $ e $ k+1 $ e un numero $ 2\ mod\ 3 $ e$ k+2 $)

Può andare bene anche così? O c'è qualche cosa che tralascio?

Re: longlisted 1969

Inviato: 02 giu 2015, 10:10
da Enigmatico
Ragazzi scusate, ma a questo punto non è moto più senplice ed equivalente dire che, poiché $k, k+1,k+2$ esauriscono i resti $mod3$ e la divisibilità di $f(x)$ non dipende da $k$, allora $f(m)$ è divisibile per $3$ per ogni $m$ intero?

P.S.: a cosa corrisponde longlist nell'ambito olimpionico?

Re: longlisted 1969

Inviato: 02 giu 2015, 10:19
da Talete
A questo punto si liquida in due righe con il fatto noto \[\bmod{q}\hspace{0.5cm} x\equiv y \Rightarrow p(x)\equiv p(y)\] per ogni $(x,y)\in\mathbb{Z}^2$, $q$ primo e $p(n)$ polinomio a coefficienti interi.

Longlist = shortlist nei primi anni delle IMO. Certo che per essere un problema longlisted è parecchio facile...

Re: longlisted 1969

Inviato: 02 giu 2015, 11:25
da karlosson_sul_tetto
santilli ha scritto:Domanda xD
Io so che ogni polinomio è esprimibile come :
$ (x-a_0) (x-a_1)... $
[...]
Può andare bene anche così? O c'è qualche cosa che tralascio?
Proprio per esser precisini, direi di no :P Sai che ogni polinomio è fattorizzabile in quel modo nei complessi, ovvero che $a_0, a_1, \ldots $ sono numeri complessi, nessuno ti dice che siano interi; quindi preso un polinomio tipo $n^4-n^2+30$ non ha radici reali, tanto meno intere, quindi non puoi applicarci sopra lo stesso ragionamento.


Comunque si, alla fine è un problema abbastanza ovvio, come si è detto sopra basta solo pensare mod q... o se volete fare gli sboroni lavorare in $\mathbb{Z}/q\mathbb{Z}$ e dire che con l'ipotesi si sono usati tutti gli elementi del campo :)

Re: longlisted 1969

Inviato: 02 giu 2015, 11:31
da Drago96
Puoi anche dire che $x\equiv y\pmod n\implies p(x)\equiv p(y)\pmod n$ con $n$ generico (sempre se il polinomio è a coefficienti interi): stai sommando e moltiplicando cose uguali...

Probabilmente la soluzione sarà stata una cosa del tipo:
Sia $p(x)=a_nx^n+\dots+a_1x+a_0$ con gli $a_i$ interi; osserviamo cosa accade mettendo interi con i tre resti differenti.
$p(3h)=a_n(3h)^n+\dots+3ha_1+a_0=3\cdot q(h)+a_0$ con $q$ a coefficienti interi perché è $q(x)=a_n3^{n-1}x^n+\dots+a_1x$
$p(3h+1)=a_n(3h+1)^n+\dots+a_1(3h+1)+a_0=a_n(1+3nh+\dots)+\dots+a_1(1+3h)+a_0=3\cdot r(h)+(a_n+\dots+a_1+a_0)$ con $r$ a coefficienti interi
$p(3h+2)=a_n(2^n+3nh2^{n-1}+\dots)+\dots+a_1(2+3h)+a_0=3\cdot s(h)+(a_n2^n+\dots+2a_1+a_0)$
Ma allora tre interi consecutivi coprono tutti i resti possibili nella divisione per 3, quindi scegliendo i giusti $h$ e valutando il polinomio in $k,k+1,k+2$ otteniamo $3\mid a_0$, $3\mid a_n+\dots+a_0$ e $3\mid a_n2^n+\dots+a_0$, ovvero $a_0=3\cdot k_1$, $a_0+\dots+a_n=3\cdot k_2$, $2^na_n+\dots+a_0=3\cdot k_2$ e sostituendo nelle espressioni sopra abbiamo:
$p(3h)=3\cdot(q(h)+k_0)$, $p(3h+1)=3\cdot(r(h)+k_2)$ e $p(3h+2)=3\cdot(s(h)+k_2)$. Le cose dentro le parentesi sono sempre intere, quindi $p$ è sempre multiplo di 3 perché ogni intero si scrive in uno di quei tre modi.

@santilli: stai tralasciando il fatto che le radici possono non essere intere! Ad esempio (trasformando il 3 in 5), come sopra il polinomio $x^5-x$ soddisfa le ipotesi, ma si scompone come $x(x+1)(x-1)(x+i)(x-i)$. Ora, uno volendo potrebbe andare a fare dell'aritmetica in $\mathbb C$, ma le cose si complicano assai...

EDIT: il tipo qua sopra fa lo sborone ma non fino in fondo... se andiamo a lavorare nei polinomi modulo $q$ primo $\mathbb Z/q\mathbb Z[X]$ abbiamo che valgono ancora tanti teoremi "soliti" dei polinomi, in particolare Ruffini: se $a$ è una radice, allora $x-a$ divide il polinomio; ma allora dato che per ipotesi $p$ si annulla su tutte le classi di resto possiamo dire che $x(x-1)\cdots(x-q+1)\mid p(x)$ e quindi valutando $p$ in un qualunque intero (ovvero in ogni classe di resto) abbiamo proprio che si annulla perché è della forma $x(x-1)\cdots(x-q+1)g(x)$... diciamo che è una formalizzazione del "ragionare modulo $q$" unito al tuo "guardiamo chi sono le radici" ;)

Re: longlisted 1969

Inviato: 02 giu 2015, 11:33
da Talete
@Drago: sì, lo sapevo, ma nello specifico bastava che fosse un primo ;)