Tutti i coefficienti uguali a più o meno 1

Polinomi, disuguaglianze, numeri complessi, ...
Avatar utente
pi_greco_quadro
Messaggi: 158
Iscritto il: 01 gen 1970, 01:00
Località: Verona

Tutti i coefficienti uguali a più o meno 1

Messaggio da pi_greco_quadro »

E beccatevi sto problemino che tanto mi ha fatto penare... :twisted:

Sia dato un polinomio monico di secondo grado $ \displaystyle p(x) $ a coefficienti interi. Determinare quali sono le possibili scelte di $ \displaystyle p(x) $ per cui esiste $ \displaystyle q(x) $, anch'esso a coefficienti interi, tale che i coefficienti del polinomio $ \displaystyle p(x)q(x) $ siano tutti uguali a $ \displaystyle \pm 1 $

P.S. non ne ho trovato la referenza.. chi la conoscesse è invitato ad indicarla... grazie..
Disco es cultura, metal es religion (Metal py)
"Ti credevo uno stortone.. e pure vecchio.. (Lei)"
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

dati $ ~x^2+a_1x+a_0 $ e $ ~b_2x^2+b_1x+b_0 $ con $ ~a_1,a_0,b_0,b_1,b_2\in\mathbb{Z} $, se $ ~(x^2+a_1x+a_0)(b_2x^2+b_1x+b_0) = $$ ~ b_2x^4+ (b_2a_1+b_1)x^3+ (b_2a_0+b_0+a_1b_1)x^2+ (a_1b_0+a_0b_1)x+a_0b_0 $ deve avere i coefficienti $ ~\in\{-1,1\} $ allora:

$ ~b_2\in\{-1,1\} $
$ ~a_0b_0\in\{-1,1\} $, allora $ ~a_0,b_0\in\{-1,1\} $
$ ~\pm a_1+b_1\in\{-1,1\}\Rightarrow a_1\pm b_1\in\{-1,1\} $
$ ~a_1b_1+(\pm a_0+b_0)\in\{-1,1\}\Rightarrow a_1b_1\in\{-3,-1,1,3\} $, allora $ ~a_1,b_1\in J=\{-3,-1,1,3\} $
ma presi due elementi di $ ~J $, la loro somma o la loro differenza non e' $ ~\in\{-1,1\} $

edit: soluzione non completa dato che q e' di grado qualsiasi. comunque questo prova che per n=2 non e' possibile :D
Ultima modifica di SkZ il 09 nov 2006, 23:50, modificato 4 volte in totale.
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Avatar utente
Sisifo
Messaggi: 604
Iscritto il: 01 gen 1970, 01:00
Località: Scorzè (VE)/Pisa

Messaggio da Sisifo »

Scusa Skz ma non capisco perchè q(x) deve essere di 2o grado
"Non è certo che tutto sia incerto"(B. Pascal)
Membro dell'associazione "Matematici per la messa al bando del sudoku" fondata da fph
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

perche' mi sono sbagliato! :oops:
all'inizio li avevo presi entrambi monici. dato la semplicita' ho riletto e mi sono accorto che q non lo era.
ma mi era scappato che non e' specificato il grado
Infatti dato l'incipit del post di $ ~\pi^2 $ temevo di aver fatto un altro errore: ecco dov'era
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
rargh
Messaggi: 136
Iscritto il: 01 mag 2005, 13:13
Località: Milano

Messaggio da rargh »

vuoi vedere se esiste q, prendiamo per semplicità q di primo grado.

P(x)=a2*x^2+a1*x+a0

Q(x)=b1*x+b0

c3=a2*b1

|c3|=1 quindi |a2|=1 e |b1|=1

c0=a0*b0

|c0|=1 quindi |a0|=1 e |b0|=1

c2=a2*b0+a1*b1

|c2|=1 quindi |a2*b0+a1*b1|=1

|a2*b0|+|a1*b1|=1 oppure ||a2*b0|-|a1*b1||=1

quindi |a1|=0 oppure |a1|=2

proviamo un po':

caso 1: |a1|=0

|c2|=1 per forza, ok siamo a posto

caso 2: |a1|=2

1=-1+2

ok
Avatar utente
pi_greco_quadro
Messaggi: 158
Iscritto il: 01 gen 1970, 01:00
Località: Verona

Messaggio da pi_greco_quadro »

Alt Alt... Il tuo problema Rargh è che stai particolareggiando il problema.. chi ti dice che non ci siano altri valori di $ \displaystyle p(x) $ per cui è possibile soddisfare le richieste del problema? Cioè non puoi prendere $ \displaystyle q(x) $ di primo grado perché è comodo, perché è il principio stesso che usi ad essere sbagliato.. non so se mi spiego
Disco es cultura, metal es religion (Metal py)
"Ti credevo uno stortone.. e pure vecchio.. (Lei)"
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

ripariamo:
sia $ ~q(x)=\sum_0^n_i b_ix^i \quad p(x)=x^2+a_1x+a_0 $
$ \dispalystyle p(x)q(x)=b_nx^{n+2}+(b_na_1+b_{n-1})x^{n+1}+ $ $ \dispalystyle \sum_2^n_i (b_ia_0+b_{i-1}a_1+b_{i-2})x^i+(a_0b_1+a_1b_0)x +a_0b_0 $
Abbiamo n+3 coefficienti e n+3 equazioni, quindi il sistema e' sempre univocamente determinato. Quindi per ognuna delle $ ~2^{n+2} $ configurazioni diverse abbiamo una soluzione se esiste
Come sopra $ ~b_n, a_0,b_0\in I=\{-1,1\} $. Con un rapido controllo si puo' vedere che si puo' prendere $ ~b_n=1 $ senza perdere in generalita' (quindi prenderlo monico non era stato un errore :D ), ovvero p(x) puo' anche non essere monico, in tal caso $ ~a_2\in I $.
Permettetemi qualche abbreviazione nelle formule, anche se non troppo corrette formalmente (ad es. i $ ~\pm $ hanno ognuno "vita" a se stante)
Posto $ ~B_0=I=\{-1,1\} $
per $ ~n=0 $, allora $ ~b_0,a_0, a_1\in B_0 $
per $ ~n=1 $, allora $ ~b_0,b_1,a_0\in B_0 $; $ ~a_1\in B_0\oplus B_0=\{-2,0,2\} $, ma va bene solo $ ~a_1=0 $
per $ ~n=2 $, non funzia (se prima non ho fatto errori)
per $ ~n=3 $, wip(*)
per $ ~n\ge 4 $ abbiamo che
$ ~b_i\pm a_1b_{i-1}\pm b_{i-2}\in I $ ovvero $ ~b_{i-2}+ a_1b_{i-1}\pm b_i \in I $
$ ~b_0,b_n\in B_0 $; $ ~ b_1,b_{n-1}\in B_1=a_1B_0\oplus B_0=\{\pm a_1\pm 1\} $; $ ~b_k,b_{n-k}\in B_k=a_1B_{k-1}\oplus B_{k-2}\oplus I,\;k\in [2;\lfloor\frac{n}{2}\rfloor] $
per ora cio'. un attimo e vediamo quando n va bene

NB: editato varie volte per correggere e migliorare

(*) work in progress
Ultima modifica di SkZ il 10 nov 2006, 06:57, modificato 6 volte in totale.
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Poeth
Messaggi: 37
Iscritto il: 17 giu 2006, 14:46

Messaggio da Poeth »

dati $ ~p(x)=x^2+ax+b $
e $ ~q(x)=c_0+c_1x+c_2x^2+....+c_nx^n $
con $ ~a,b,c_i \in\mathbb{Z} $

la seguente formula va bene con q di grado abbastanza alto... se ha pochi termini non c'è bisogno dell'i-esimo elemento

$ ~p(x)q(x) = bc_0+x(bc_1+ac_0)+ $....$ ~+x^i( bc_i + ac_{i-1} + c_{i-2} )+ $....$ ~+ x^{n+1}(ac_n+c_{n-1})+x^{n+2}(c_n) $
per i che va da 2 a n.

Osservando il primo termine abbiamo:
$ ~ bc_0\in\{-1,1\} $, allora $ ~b,c_0\in\{-1,1\} $

Ora prendiamo in esame il coefficiente di $ ~x^2 $ in modulo.

$ ~ 1= |bc_2+ac_1+c_0| $
$ ~ 1= |bc_2+ac_1+c_0| =< |bc_2|+|ac_1+c_0| $
ma b è -1 o +1, quindi non influenza il modulo
$ ~ 1=|bc_2+ac_1+c_0| =< |c_2|+|ac_1+c_0| $
$ ~ 1=|bc_2+ac_1+c_0| =< |c_2|+|ac_1+c_0| =< |c_2|+|ac_1|+|c_0| $
ma c con 0 è +1 o -1
$ ~ 1=|bc_2+ac_1+c_0| =< |c_2|+|ac_1+c_0| =< |c_2|+|ac_1|+1 $
che è vero solo per
$ ~ c_2 =0; ac_1 =0 $

ovvero preso $ ~ c_2 $ a piacere $ ~ \in\mathbb{Z} $, abbiamo dimostrato che $ ~ c_2=0 $, il che è assurdo. Non esiste p(x) che vada bene per un q(x) che contenga un termine di secondo grado.


Correggetemi se ho sbagliato eh che è tardi :p:D
Ecco le prime buffe formule che ho scoperto.... ne sono fierissimo anche se sono inutili :D

[tex]\pi \simeq 10*(\sqrt{2} - 1) -1

e\pi(\pi+e) \simeq (\frac{10}{\sqrt2})^{2}

2*phi \simeq 1+ \sqrt{\frac{e\pi(e+\pi)}{10}}
[/tex]
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

dimenticavo che avanzano un'equazione per le pari e 2 per le dispari
se n=2m abbiamo anche $ ~b_{m-1}+a_1b_m\pm b_{m+1}\in I $ quindi
$ ~a_1b_m\in a_1B_{m}=I\oplus B_{m-1}\oplus B_{m-1} $
se n=2m+1 abbiamo anche $ ~b_{m-1}+a_1b_m\pm b_{m+1}\in I $ con $ ~b_m, b_{m+1}\in B_{m} $ quindi $ ~b_{m-1}\in B_{m-1}=I\oplus a_1B_{m}\oplus B_{m} $

$ ~B_k $ e' l'insieme delle possibili $ ~b_k, b_{n-k} $. si evince che $ ~x\in B_k\Rightarrow -x\in B_k $
non so a cosa possa servire tutto sta roba che ho scritto, ma a me piace! :D

pi_greco_quadro ha scritto:E beccatevi sto problemino che tanto mi ha fatto penare... :twisted:
porca! gia' per n=3 a farlo a mano non e' semplicissimo
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
rargh
Messaggi: 136
Iscritto il: 01 mag 2005, 13:13
Località: Milano

Messaggio da rargh »

eh ok lo so era solo una soluzione particolare.

C´ho perso un po di tempo ma non sono riuscito a risolverlo in generale, ho trovato solo alcuni esempi (per esempio se ponevo a1=1 dovevo prendere q(x) di terzo grado))

Abbiamo visto che a2 e a0 devono essere per forza pari a +- 1 .

Forse si potrebbe risolvere il problema in questo modo: dato un certo a1, posso trovare un polinomio q(x) di grado FINITO che mi risolva il problema?

Per esempio, proviamo a mettere a1=3, e cerchiamo q(x) nelle varie possibilita´(ovviamente abbiamo due casi, a1*a0=+1 e a1*a0=-1... vediamo se troviamo un q(x) per entrambi i casi).

Da qui in poi non so generalizzare... non sono sicuro se esiste un q(x) per ogni possibile a1 inero... se esiste, immagino che piu e´grande in valore assoluto a1 e piu´sara alto il grado di q(x) ...
rargh
Messaggi: 136
Iscritto il: 01 mag 2005, 13:13
Località: Milano

Messaggio da rargh »

ho notato una cosa curiosa:

se a1 e´ dispari, allora q(x) dev´essere di grado pari a 3k (multiplo di 3) cioe´ci devono essere 3k+1 termini bi

se a1 e´ pari, allora q(x) dev´essere di grado pari a 4k+1 cioe´ ci devono essere 4k+2 termini bi

viene tutto da´considerazioni su parita o disparita dall´equazione:

c_i=a2*b_(i-2)+a1*b_(i-1)+a0*b_(i-2)

sappiamo che a2 e a0 hanno modulo unitario quindi sono dispari. c_i deve avere modulo unitario quindi e' dispari anche lui.

sappiamo inoltre che b_n e b_0 hanno modulo unitario, quindi sono dispari anche loro.

Usando tutto questo arriviamo alla conclusione:

se a1 e' dispari allora, la sequenza di parita e disparita di q(x) sara´ data da:

DPPDPPDPP.........DPPDPPD

cioe´ k volte DPP piu D alla fine

se a1 e´ dispari allora

DDPPDDPP....DDPPDDPPDDPPDD

cioe´ k volte DDPP piu DD alla fine
rargh
Messaggi: 136
Iscritto il: 01 mag 2005, 13:13
Località: Milano

Messaggio da rargh »

forse ho trovato la soluzione:

allora, prendiamo per buono adesso che esistono soluzioni per abs(a1)<2>=3

Ora cerchiamo di costruire Q(x).

Iniziamo con queste equazioni:

abs(a0*b0)=1
abs(a0*b1+a1*b0)=1

e in generale

abs(a0*b_(i+2)+a1*b_(i+1)+a2*bi)=1

supponendo di avere trovato b_i e b_(i+1) troviamo b_(i+2) che rispetti questa condizione.

Ora vogliamo che Q(x) sia di grado finito, quindi deve esistere i finito per cui b_(i+2)=0 e´ una soluzione.

Nell´ipotesi che abs(a1)>=3 vediamo che i vari b_i possono solo crescere in valore assoluto.

Procediamo per induzione:


usiamo la solita equazione:

abs(a0*b_(i+2)+a1*b_(i+1)+a2*bi)=1

e dimostriamo che se abs(b_(i+1))>abs(b_i) allora abs(b_(i+2)>abs(b_(i+1))


Sappiamo che abs(a0)=abs(a2)=1

tra i vari possibili b_(i+2) che risolvono quell´equazone, quello con valore assoluto piu basso e´:

min(abs(b_(i+2))=abs(a1*b_(i+1))-abs(bi)-1


vediamo che : abs(b_(i+2)>abs(b_(i+1))

cioe che:

abs(a1*b_(i+1))-abs(bi)-1-abs(b_(i+1))>0

infatti:

abs(a1*b_(i+1))-abs(bi)-1-abs(b_(i+1))=abs(b_(i+1))*(abs(a1)-1)-abs(bi)-1>=2abs(b_(i+1))-)-abs(bi)-1>abs(b_(i+1))-1>0


la condizione iniziale e:

abs(b_(0))=1

abs(b_(1))=abs(a1)+-1>=2>1

quindi abbiamo abs(b1)>abs(b(0)), abs(b1)-1>0

da questo vediamo che per ogni i>=0

abs(i+2)>abs(i+1)>1
Avatar utente
pi_greco_quadro
Messaggi: 158
Iscritto il: 01 gen 1970, 01:00
Località: Verona

Messaggio da pi_greco_quadro »

Quindi in definitiva come sono fatti i $ \displaystyle p(x) $ richiesti dal problema?
Disco es cultura, metal es religion (Metal py)
"Ti credevo uno stortone.. e pure vecchio.. (Lei)"
rargh
Messaggi: 136
Iscritto il: 01 mag 2005, 13:13
Località: Milano

Messaggio da rargh »

beh in definitiva, p(x) deve avere questa forma:

abs(a2)=1

abs(a1)=0,1,2

abs(a0)=1

con qualsiasi combinazione dei segni di a2,a1 e a0

per favore aiutatemi a smettere sti problemi sono ossessivi e io sono pure lento...
rargh
Messaggi: 136
Iscritto il: 01 mag 2005, 13:13
Località: Milano

Messaggio da rargh »

per chi vuole impazzire, sapete trovare la risposta quando p(x) è di grado qualsiasi?
Rispondi