longlisted 1969

Polinomi, disuguaglianze, numeri complessi, ...
Rispondi
Avatar utente
luca95
Messaggi: 65
Iscritto il: 09 set 2014, 19:19
Località: Firenze, Udine

longlisted 1969

Messaggio da luca95 » 30 mag 2015, 22:23

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 $.

Enigmatico
Messaggi: 79
Iscritto il: 03 dic 2014, 23:23

Re: longlisted 1969

Messaggio da Enigmatico » 31 mag 2015, 22:20

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$.

matpro98
Messaggi: 458
Iscritto il: 22 feb 2014, 18:42

Re: longlisted 1969

Messaggio da matpro98 » 31 mag 2015, 22:47

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?

Avatar utente
luca95
Messaggi: 65
Iscritto il: 09 set 2014, 19:19
Località: Firenze, Udine

Re: longlisted 1969

Messaggio da luca95 » 31 mag 2015, 23:28

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

Enigmatico
Messaggi: 79
Iscritto il: 03 dic 2014, 23:23

Re: longlisted 1969

Messaggio da Enigmatico » 01 giu 2015, 14:17

Avete ragione, l'ho sparata grossa... Nel pomeriggio provo a correggermi!

Avatar utente
6frusciante9
Messaggi: 46
Iscritto il: 12 mar 2015, 17:47
Località: Rimini

Re: longlisted 1969

Messaggio da 6frusciante9 » 01 giu 2015, 15:18

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 $
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te

Avatar utente
luca95
Messaggi: 65
Iscritto il: 09 set 2014, 19:19
Località: Firenze, Udine

Re: longlisted 1969

Messaggio da luca95 » 01 giu 2015, 17:11

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 $

Avatar utente
6frusciante9
Messaggi: 46
Iscritto il: 12 mar 2015, 17:47
Località: Rimini

Re: longlisted 1969

Messaggio da 6frusciante9 » 01 giu 2015, 17:40

Si in effetti credo si posa generalizzare abbastanza agevolmente ...
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te

santilli
Messaggi: 24
Iscritto il: 30 set 2014, 20:59
Località: Rovigo

Re: longlisted 1969

Messaggio da santilli » 02 giu 2015, 09:30

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?
16 esimi GAS '2016 :D finalmenteeeee! #RovigoPower xD

Enigmatico
Messaggi: 79
Iscritto il: 03 dic 2014, 23:23

Re: longlisted 1969

Messaggio da Enigmatico » 02 giu 2015, 10:10

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?

Talete
Messaggi: 744
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: longlisted 1969

Messaggio da Talete » 02 giu 2015, 10:19

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...
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

Avatar utente
karlosson_sul_tetto
Messaggi: 1436
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: longlisted 1969

Messaggio da karlosson_sul_tetto » 02 giu 2015, 11:25

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 :)
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

Avatar utente
Drago96
Messaggi: 1144
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: longlisted 1969

Messaggio da Drago96 » 02 giu 2015, 11:31

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" ;)
Ultima modifica di Drago96 il 02 giu 2015, 11:48, modificato 1 volta in totale.
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Talete
Messaggi: 744
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: longlisted 1969

Messaggio da Talete » 02 giu 2015, 11:33

@Drago: sì, lo sapevo, ma nello specifico bastava che fosse un primo ;)
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

Rispondi