Tenho um polinômio P, com coeficientes inteiros e não-negativos. Você pode me perguntar o valor de P(x) para qualquer número x algébrico. Quantas perguntas são suficientes para que você seja capaz de descobrir os coeficientes de P? Como proceder?
Edição: note que você não sabe qual é o grau do polinômio.
(Baseado no post A puzzle about polynomials (God Plays Dice))
André
javendo
aaronalb
Pietro
ynotx
Luís Guilherme Fernandes Pereira
mariogen
abgrilo
Bacana o problema. Lembra que estávamos conversando sobre se daria pra descobrir o polinômio sabendo só que seus coeficientes são inteiros; estabelecemos que se puderem ser racionais ou reais não dá pra descobrir nada, graças à interpolação de Lagrange.
Porém, depois vi que era simples adaptar nosso raciocínio pro caso inteiro. Para qualquer número finito N de perguntas, vc pode me dizer
P(a1) = … = P(aN) = 0
e eu ainda não tenho como saber se P é o polinômio nulo ou simplesmente (X-a1)*…*(X-aN). Então a positividade é fundamental.
Resta saber se conseguiríamos descobrir P caso seus coeficientes fossem racioanis (ou reais) positivos. Basta descobrir o grau do polinômio, que daí o resto sai por álgebra linear com um número finito de perguntas.
Ah! Se os coeficientes de P forem reais positivos, acho que dá pra descobrir o grau de P com 3 perguntas!
Hum, legal! Vou tentar provar!
Ops, na verdade o jeito que pensei não dá certo. Ainda não sei se é possível descobrir o polinômio com um número finito de perguntas, mas por enquanto apostaria que sim.
Consegui por outra linha de argumentação. Minha idéia errada era a seguinte, excessivamente simples (e na verdade “precisava” de duas perguntas):
Quanto é P(1)? Quanto é P(G)? Aqui G é um número muito grande “comparado com P”, em algum sentido. Inicialmente tomei como P(1)+1. Aí calcularíamos a fração
P(x)/x^k
nos pontos 1 e G (juro que isso não foi intencional, G era de “grande”), para k variando de 0 em diante.
A idéia é que, quando k é maior ou igual ao grau de P, P(x)/x^k é estritamente decrescente — aqui usamos que os coeficientes são positivos. O meu erro foi achar que, para k *menor* que o grau de P, P(x)/x^k seria crescente.
Então bastaria ver qual o primeiro k pro qual P(x)/x^k é decrescente, e teríamos o grau.
O problema é que a segunda parte não é verdade. De fato, se k<grau(P) então P(x)/x^k é crescente a partir de certo ponto; mas pra estimar esse ponto (pra escolhermos G), é necessário estimar não só o "tamanho geral" de P (por exemplo a soma de seus coeficientes), mas a razão entre o seu coeficiente líder e o "resto" (digamos, a soma dos outros coeficientes).
Não consegui levar esse approach adiante, e no final consegui um método que, pra um polinômio de grau d, faz d+2 perguntas e determina os coeficientes. (Desde que sejam reais positivos.)
O algoritmo em si é simples, mas a prova de que funciona tem um passo bonitinho.
En el caso de coeficientes enteros es posible conocerlo con tantas preguntas como el grado ´d´.
La solución:
tras preguntar P(1) buscamos un primo q > P(1).
Preguntamos P(1/q) lo cual permite conocer el grado.
Continuamos haciendo d-2 preguntas para interpolar