Técnica olímpica - Vieta Jumping
Enviado: Seg 30 Out, 2017 02:56
As fórmulas de Vieta são conhecidas no Brasil como relações de Girard, elas relacionam as raízes de um polinômio com seus coeficientes.
Vieta Jumping ficou conhecida no meio olímpico após claramente ser cobrada na questão 6 da IMO de 1988, onde nem mesmo o jovem Terence Tao conseguiu resolvê-la completamente naquele momento.
É usada geralmente em problemas de divisibilidade.
A técnica consiste em:
1) Considerando uma solução (a,b), rearranjar a relação dada na questão como uma equação do segundo grau em "a".
2) Descobrir a segunda raiz [tex3]x_2 [/tex3] pela fórmula de Vieta (Relação de Girard)
3) Achar uma contradição envolvendo [tex3]x_2 [/tex3]
Exemplo 1)IMO 88 - Sejam a e b inteiros positivos, se [tex3]\frac{a^2+b^2}{ab+1}[/tex3] é inteiro, então prove que é quadrado perfeito.
Sem perda de generalidade: [tex3]a \geq b > 0 [/tex3]
Supondo que (a,b) seja uma solução tal que a soma a+b seja mínima.
[tex3]\frac{a^2+b^2}{ab+1} = k[/tex3]
[tex3]t^2 - tkb + b^2 -k= 0[/tex3]
Considerando como uma equação do segundo grau em "t", então "a" é uma raiz e [tex3]x_2[/tex3] a outra. Pelas fórmulas de Vieta (Relações de Girard):
[tex3]x_2 + a = kb \rightarrow x_2 = kb-a[/tex3]
[tex3]x_2 \cdot a =b^2-k \rightarrow x_2 = \frac{b^2-k}{a}[/tex3]
Da primeira sai que [tex3]x_2[/tex3] é inteiro, da segunda sai que ele é diferente de zero, já que se [tex3]x_2 = 0[/tex3] , então [tex3]k = b^2[/tex3] e está provado o enunciado.
Agora, se [tex3]x_2[/tex3] for negativo, então:
[tex3]x_2^2 - x_2kb + b^2 -k \geq x_2^2 + k+b^2 - k > 0 [/tex3]
Absurdo, já que [tex3]x_2[/tex3] é raiz da equação, então [tex3]x_2[/tex3] é inteiro e positivo.
Sendo assim, [tex3](a,x_2)[/tex3] é solução do problema.
Mas como [tex3]a \geq b[/tex3] , então:
[tex3]x_2 = \frac{b^2-k}{a} < a[/tex3]
Ou seja: [tex3]x_2 + b < a+b [/tex3]
contrariando a soma mínima, e portanto [tex3]x_2 = 0 [/tex3]
Exemplo 2) Suponha que a,b e c são inteiros positivos tais que: [tex3]0 < a^2+b^2 - abc < c [/tex3] . Mostre que [tex3]a^2+b^2 - abc [/tex3] é quadrado perfeito.
Sem perda de generalidade: [tex3]a \geq b > 0 [/tex3]
Fazendo:
[tex3]a^2+b^2 - abc = x[/tex3]
e considerando uma equação do segundo grau em "a", então "a" é uma raiz e a outra é [tex3]x_2 = \frac{b^2-x}{a}[/tex3]
Se [tex3]x_2 = \frac{b^2-x}{a} = 0[/tex3] , então [tex3]b^2 = x[/tex3] e o enunciado está provado.
Se [tex3]x_2 = \frac{b^2-x}{a} < 0[/tex3] então:
[tex3]0 =x_2^2+b^2 - x_2 bc - x > x_2^2+b^2 - x_2bc - c \geq 0 [/tex3]
Absurdo, então [tex3]x_2[/tex3] é positivo e inteiro, logo [tex3](a,x_2)[/tex3] é solução do problema
Mas [tex3]x_2 < \frac{b^2}{a} \leq b[/tex3] .
Então com uma solução (a,b) é possível sempre encontrar uma menor [tex3](a,x_2) [/tex3] e assim indefinidamente.... Mas é um absurdo, já que uma hora um dos 2 números será igual a zero.
Então realmente [tex3]x_2 = 0 [/tex3]
Vieta Jumping ficou conhecida no meio olímpico após claramente ser cobrada na questão 6 da IMO de 1988, onde nem mesmo o jovem Terence Tao conseguiu resolvê-la completamente naquele momento.
É usada geralmente em problemas de divisibilidade.
A técnica consiste em:
1) Considerando uma solução (a,b), rearranjar a relação dada na questão como uma equação do segundo grau em "a".
2) Descobrir a segunda raiz [tex3]x_2 [/tex3] pela fórmula de Vieta (Relação de Girard)
3) Achar uma contradição envolvendo [tex3]x_2 [/tex3]
Exemplo 1)IMO 88 - Sejam a e b inteiros positivos, se [tex3]\frac{a^2+b^2}{ab+1}[/tex3] é inteiro, então prove que é quadrado perfeito.
Sem perda de generalidade: [tex3]a \geq b > 0 [/tex3]
Supondo que (a,b) seja uma solução tal que a soma a+b seja mínima.
[tex3]\frac{a^2+b^2}{ab+1} = k[/tex3]
[tex3]t^2 - tkb + b^2 -k= 0[/tex3]
Considerando como uma equação do segundo grau em "t", então "a" é uma raiz e [tex3]x_2[/tex3] a outra. Pelas fórmulas de Vieta (Relações de Girard):
[tex3]x_2 + a = kb \rightarrow x_2 = kb-a[/tex3]
[tex3]x_2 \cdot a =b^2-k \rightarrow x_2 = \frac{b^2-k}{a}[/tex3]
Da primeira sai que [tex3]x_2[/tex3] é inteiro, da segunda sai que ele é diferente de zero, já que se [tex3]x_2 = 0[/tex3] , então [tex3]k = b^2[/tex3] e está provado o enunciado.
Agora, se [tex3]x_2[/tex3] for negativo, então:
[tex3]x_2^2 - x_2kb + b^2 -k \geq x_2^2 + k+b^2 - k > 0 [/tex3]
Absurdo, já que [tex3]x_2[/tex3] é raiz da equação, então [tex3]x_2[/tex3] é inteiro e positivo.
Sendo assim, [tex3](a,x_2)[/tex3] é solução do problema.
Mas como [tex3]a \geq b[/tex3] , então:
[tex3]x_2 = \frac{b^2-k}{a} < a[/tex3]
Ou seja: [tex3]x_2 + b < a+b [/tex3]
contrariando a soma mínima, e portanto [tex3]x_2 = 0 [/tex3]
Exemplo 2) Suponha que a,b e c são inteiros positivos tais que: [tex3]0 < a^2+b^2 - abc < c [/tex3] . Mostre que [tex3]a^2+b^2 - abc [/tex3] é quadrado perfeito.
Sem perda de generalidade: [tex3]a \geq b > 0 [/tex3]
Fazendo:
[tex3]a^2+b^2 - abc = x[/tex3]
e considerando uma equação do segundo grau em "a", então "a" é uma raiz e a outra é [tex3]x_2 = \frac{b^2-x}{a}[/tex3]
Se [tex3]x_2 = \frac{b^2-x}{a} = 0[/tex3] , então [tex3]b^2 = x[/tex3] e o enunciado está provado.
Se [tex3]x_2 = \frac{b^2-x}{a} < 0[/tex3] então:
[tex3]0 =x_2^2+b^2 - x_2 bc - x > x_2^2+b^2 - x_2bc - c \geq 0 [/tex3]
Absurdo, então [tex3]x_2[/tex3] é positivo e inteiro, logo [tex3](a,x_2)[/tex3] é solução do problema
Mas [tex3]x_2 < \frac{b^2}{a} \leq b[/tex3] .
Então com uma solução (a,b) é possível sempre encontrar uma menor [tex3](a,x_2) [/tex3] e assim indefinidamente.... Mas é um absurdo, já que uma hora um dos 2 números será igual a zero.
Então realmente [tex3]x_2 = 0 [/tex3]