Додаток: перестановка коренів, Vieta jumping, раціональні точки на квадриках

Vieta Jumping

By now, Vieta jumping has become a standard technique for solving some particular type of olympiad number theory problems. It is also known as Root Jumping or Root Flipping. Though it involves Diophantine equations and for now, it is out of our scope, many divisibility or congruence problems can be turned into one that can be solved using this tactic. Hence, this section.

To understand just how popular it has been, let's just mention that there are at least two IMO problems that have standard solutions using this particular technique. And surely, there are many other olympiad problems that fall into the same category. Now, let's see what it is and what it actually does.

Consider the following quadratic equation. \begin{align*} ax^2+bx+c & = 0 \end{align*} According to Vieta's formula, if two of its roots are $x_1$ and $x_2$, then \begin{align*} x_1+x_2 & = -\dfrac{b}{a}\ x_1x_2 & = \dfrac{c}{a} \end{align*} Vieta jumping relies on these two equations. It is in fact, a descent method in which we usually prefer using one of the following two methods:

1. Standard Descent: It is usually used to show that the equation doesn't have any solution or some sort of contradiction to prove a claim, like we do in Infinite Descent. For a solution $(x,y)$ of the equation, we define a function dependent on $x,y$ ($x+y$ is such a common function, as we will see later). Then we consider the solution that minimizes that function over all solutions possible. If there are multiple solutions that can achieve this, we are free to choose any one depending on the problem. But then, using Vieta's formulas, we try to find another solution that makes the function's value smaller, which gives us the necessary contradiction. So, this is a modified version of infinite descent.

2. Constant Descending: Sometimes, we take some constants, for example, an integer $k$ and fix it for the whole problem. For a solution $(a,b)$, we fix $b$ and $k$. Then using those formulas, we find a solution $x$ so that $0<x<b$ so that it produces a solution $(b,x)$ smaller than $(a,b)$. Note that, here, we have to take $b<a$ so that the new solution is guaranteed to be smaller. Repeating this, we will reach a base case and those constants ($k$, for example) will remain constant through the whole process. Thus, we will show what's required.

3. Sometimes, there can be even geometric interpretations. For example, Arthur Engel showed one in his book Problem Solving Strategiesm chapter $6$, problem $15$.

We will now demonstrate this using some example problems. Let's start with the classical problem from IMO $1988$. Here is what Engel said about this problem in his book:

Nobody of the six members of the Australian problem committee could solve it. Two of the members were George Szekeres and his wife Esther Klein, both famous problem solvers and problem creators. Since it was a number theoretic problem it was sent to the four most renowned Australian number theorists. They were asked to work on it for six hours. None of them could solve it in this time. The problem committee submitted it to the jury of the XXIX IMO marked with a double asterisk, which meant a superhard problem, possibly too hard to pose. After a long discussion, the jury finally had the courage to choose it as the last problem of the competition. Eleven students gave perfect solutions.

1. [IMO $1988$, Problem $6$] Let $a$ and $b$ be two positive integers such that $ab + 1$ divides $a^{2} + b^{2}$. Show that $\dfrac{a^{2}+b^{2}}{ab+1}$ is a perfect square.

Solution: Let $k$ be an integer so that \begin{align*} \dfrac{a^2+b^2}{ab+1} & = k\newline a^2+b^2 & = kab+k\newline a^2-kab+b^2-k & = 0 \end{align*} As we said in the process, we will fix $k$ and consider all pairs of integers $(a,b)$ that gives us $k$ as the quotient. And take a solution $(a,b)$ in nonnegative integers so that the sum $a+b$ is minimum (and if there are multiple such $(a,b)$, we take an arbitrary one). Without loss of generality, we can assume $a\geq b>0$. Now, fix $b$ and set $a=x$ which will be the variable. We get an equation which is quadratic in $x$ with a root $a$. \begin{align*} x^2-kbx+b^2-k & = 0 \end{align*} Using Vieta, we get that $x+a=kb$ or $x=kb-a$. From this, we infer $x$ is integer Note that, we can write it another way, \begin{align*} x & = \dfrac{b^2-k}{a} \end{align*} This equation will do the talking now! Firstly, if $x=0$, we are done since that would give us $b^2-k=0$ or $k=b^2$, a perfect square. So, we can assume that $x\neq0$. To descend the solution, we will need $x>0$. For the sake of contradiction, take $x=-z$ where $z>0$. But that would give us, \begin{align*} x^2-kbx+b^2-k & = z^2+kbz+b^2-k\newline &\geq z^2+k+b^2-k\newline & = z^2+b^2\newline & > 0 \end{align*} This is impossible. Thus, $x>0$ and now, if we can prove that $0<x<a$, then we will have a solution $(x,b)$ smaller than $(a,b)$. We actually have this already because \begin{align*} x & = \dfrac{b^2-k}{a}\newline & < \dfrac{b^2}{a}\text { since } k\text { is a positive integer}\newline &\leq\dfrac{a^2}{a}\newline & = a \end{align*} Therefore, we must have a solution $(0,b)$ for the equation which gives us $k=b^2$.

1. Let $a$ and $b$ be positive integers such that $ab$ divides $a^2 + b^2 + 1$. Prove that $a^2 + b^2 + 1=3ab$.

Solution: Again, let $k=\dfrac{a^2+b^2+1}{ab}$ and among all the solutions of the equation, consider the solution that minimizes the sum $a+b$. We can also assume that, $a\geq b$. Now we rewrite it for applying Vieta. \begin{align*} a^2-kab+b^2+1 & = 0 \end{align*} Just like before, let's fix $b$ and make it quadratic in $x$, which already has a solution $a$. \begin{align*} x^2-kbx+b^2+1 & = 0 \end{align*} For the other solution, \begin{align*} x & = \dfrac{b^2+1}{a}\newline & = kb-a \end{align*} The first implies that $x$ is positive and the last equation implies that $x$ is an integer. Now, if $a=b$, we already get that $k=\dfrac{1^2+1^2+1}{1\cdot1}=3$. So we are left with $a>b$. But then, \begin{align*} x & = \dfrac{b^2+1}{a}\newline & < \dfrac{b^2+2b+1}{a}\newline & = \dfrac{(b+1)^2}{a}\newline &\leq\dfrac{a^2}{a}\newline & = a \end{align*} which again produces a smaller sum $x+b<a+b$. This is a contradiction, so $a=b$ must happen.

(IMO $2007$, Problem $5$). Let $a$ and $b$ be positive integers so that $4ab − 1$ divides $(4a^2 − 1)^2$. Prove that $a = b$.

In short: If $4ab-1$ does not divide into $4a^2-1$, it must be a perfect square, but it can't be. If $4ab-1$ divides into $4a^2-1$, it will divide into $b-a$, but it can't be.

Solution by Jiazhen Tan

Prove that, for any positive integer $k$, there are positive integers $a, b > 1$ such that

$$k=\dfrac{a^2+b^2-1}{ab}$$

Let $a,b$ be positive integers such that $ab-1$ divides $a^2+b^2$. Prove that their quotient is $5$.

Being the lazy person I am, I'll just outline my attempt (use it as a hint maybe):

Let $a^2+b^2=k(ab-1)$. WLOG $a>b$. Rewrite it as a single variable quadratic. If $k\geq b(a-b)$, bad things happen, so the other solution is $x<b$. This creates and infinite descent and it will eventually drop to $1$ or $0$. $2^2+1^2=5*1$.

Solution by Jiazhen Tan

Let $a, b,$ and $c$ be positive integers such that $0 < a^2+b^2-abc \leq c$. Prove that $a^2+b^2-abc$ is a perfect square.

WLOG assume $a\geq b$.

Denote the set $S_{k,c}=\{(a,b):k=a^2+b^2-abc, 0<k\leq c\}$.

$$a^2+b^2-abc=k\\ a^2+b^2-abc-k=0\\ a^2-bca+(b^2-k)=0$$

Replace $a$ with a variable $x$ to yield $$x^2-bcx+(b^2-k)=0$$

Let $(x,b)\in S_{k,c}$. By Vieta's formulas, $$\begin{cases} a+x=bc\\ ax=b^2-k \end{cases}$$

so . Since $k>0$, . Since we assumed $a\geq b$, $\frac{b^2}{a}\ \leq b$. Thus $$x=\frac{b^2-k}{a}\ <b$$

We can prove $x\geq0$ by contradiction. Suppose $x<0$. Using the given condition that $a^2+b^2-abc\leq c$, we get

$$c\geq k\\ -k\geq -c\\ x^2-bcx+b^2-k\geq x^2-bcx+b^2-c\\ =x^2+b^2-c(bx+1)$$

Since $b\in\mathbb{N}$ and $x<0$, $bx\leq-1$, so $-(bx+1)\geq0$. Thus $$-c(bx+1)\geq0\\ x^2+b^2-c(bx+1)>0$$

This is a contradiction because $x^2+b^2-c(bx+1)=0$ from equation. This means that $x\geq0$.

Therefore, given one solution we can generate an infinite sequence of solutions $(b,bc-a)\in S_{k,c}$. Since $0\leq x<b\leq a$, $a$ is bounded below by 0 so $\exists a_m:(a_m,0)\in S_{k,c}$. $k$ is fixed, so $k=b^2$ when $a_m=0$. $\Box$

Solution by Catherine Yeo