Pagina 1 di 1

Polinomi a coefficienti interi noto p(a)

MessaggioInviato: 21/04/2018, 16:08
da G64
Supponiamo che di un polinomio a coefficienti interi io conosca il valore in a: quali sono i possibili valori che può assumere in b? L'unica restrizione viene da [tex]b-a|p(b)-p(a)[/tex] oppure esistono altri vincoli? E se conosco il valore in 2, 3, [tex]n[/tex] punti?
Insomma a me pare che l'unica restrizione sia quel lemma, però per sicurezza chiedo :D

Re: Polinomi a coefficienti interi noto p(a)

MessaggioInviato: 26/04/2018, 13:42
da afullo
Se conosci il valore in [tex]a[/tex], allora in [tex]b[/tex] può assumere qualunque valore a patto che soddisfi quella condizione. Infatti, questa si può scrivere come [tex]p(b)-p(a) = m \cdot (b-a)[/tex], dove [tex]m[/tex] è un'opportuna costante intera; considerando ora il polinomio di primo grado [tex]p(x) = m \cdot (x-a) + p(a)[/tex], dove [tex]p(a)[/tex] è appunto una quantità nota (quindi possiamo definire il polinomio [tex]p[/tex] conoscendola, altrimenti la definizione sarebbe circolare :mrgreen: ), osserviamo che al variare di [tex]m \in \mathbb{Z}[/tex] otteniamo tutti e soli i casi possibili.

Per esempio, per [tex]m=0[/tex] otteniamo il polinomio costante, per cui [tex]p(b)-p(a)=0[/tex], per [tex]m=1[/tex] quello per il quale [tex]p(b)-p(a)=b-a[/tex], per [tex]m=2[/tex] quello per cui [tex]p(b)-p(a)=2(b-a)[/tex], e così via; pertanto, se da una parte è possibile ottenere per la quantità [tex]p(b)-p(a)[/tex] solo multipli di [tex]b-a[/tex] (è ciò che afferma quel vincolo), dall'altra è possibile ottenere tutti i multipli di [tex]b-a[/tex], quindi esattamente quelli.

Re: Polinomi a coefficienti interi noto p(a)

MessaggioInviato: 30/04/2018, 17:00
da G64
Perfetto, grazie mille!

Re: Polinomi a coefficienti interi noto p(a)

MessaggioInviato: 30/04/2018, 19:53
da afullo
Per più punti tale requisito è sicuramente una condizione necessaria per tutte le coppie, *penso* che sia anche sufficiente pure se non mi viene una dimostrazione al volo, direi che si possa provare a vedere cosa succede nella tabella delle differenze divise di Newton...

Re: Polinomi a coefficienti interi noto p(a)

MessaggioInviato: 30/04/2018, 22:33
da Lasker
Beh non si può dimostrare perché il caso generale è falso, un controesempio che mi è capitato di trovare in gara è il problema $19$ della finale GaS $2013$. La condizione è necessaria ma non sufficiente.

Per costruire un esempio, prendi un polinomio a coefficienti interi tale che $p(2)=6,p(4)=4, p(6)=2$, e chiediti quanto può valere $p(8)$, il lemma ci dice $6|p(8), 4|p(8), 2|p(8)$ che si riassumono in $12|p(8)$, ma vale anche $p(x)=(x-2)(x-4)(x-6)R(x)+8-x$, da cui $p(8)=6\cdot 4\cdot 2 \cdot R(8)$ che è sempre multiplo di $48$ visto che $R$ è a coefficienti interi e quindi tipo $p(8)=12$ non si combina a farlo.

Re: Polinomi a coefficienti interi noto p(a)

MessaggioInviato: 01/05/2018, 9:04
da afullo
Ah ecco. Io avevo fatto alla veloce qualche prova con Newton e mi tornava sempre, però già solo con due punti dati e la ricerca delle possibilità di passaggio per un terzo nei calcoli generali ci si arenava...