13tn European Girls' Mathematical Olympiad (EGMO 2024)

Problem 1. Two different integers u and v are written on a board. We perform a sequence of steps.At each step we do one of the following two operations:
(i) If a and b are different integers on the board, then we can write a + b on the board, if it is not already there.
(ii) If a, b and c are three different integers on the board, and if an integer x satisfies ax² + bx + c = 0, then we can write x on the board, if it is not already there.
Determine all pairs of starting numbers ( u, v ) from which any integer can eventually be written on the board after a fi nite sequence of steps.

Solution

Let a pair $(u,v)$ which allows us to write the entire set of integers on the blackboard good. We claim that all pairs $(u,v)$ such that $u,v\neq 0$ , atleast one of $u,v$ is positive and $(u,v) \neq (-1,1),(1,-1)$ are good. First we eliminate the bad pairs.

Clearly, if $u=0$ or $v=0$ , then no other new numbers can be created using move (i) and thus, we cannot create any other new numbers. Further, if the starting pair is $(1,-1)$ , the only new number we can create using move (i) is 0. Thus, the only polynomials of the form $ax^2+bx+c$ we can form are $x^2-1$ (which has roots $1,-1$ ), $-x^2+1$ (which has the same roots), $-x^2+x$ (which has the roots $0$ and $-1$ ), $x^2-x$ (which has the same roots), $x-1$ (which has the root $1$ ) and $-x+1$ (which has the same root). Thus, no new numbers can be created as claimed. Further, if both $(u,v)$ are negative, any new numbers formed by rule (i) will also be negative. Further, any polynomial of the given form will have negative coefficients and thus,
$-ax^2-bx-c=0 \implies - (ax^2+bx+c)=0$ for positive $a,b,c$ . Thus, if this factors as $-(x-r_1)(x-r_2)$ we see that $r_1$ and $r_2$ must both be negative for $a,b,c$ to all be positive. Thus, the roots of this equation are negative which implies that rule (ii) also creates only negative numbers.

Now, we show that all other numbers are good. We first prove the following claim.
Claim : All pairs of the form $(1,n)$ for some integer $n$ are good.
Proof : Note that using rule (i), we can write all integers greater than $n$ . In particular, we can create arbitrarily large positive integers. Now, this means for all sufficiently large positive $k$ , we can write the numbers $2k$ and $k^2$ on the board. Thus,
$x^2+2kx+k^2=0 \implies (x+k)^2=0$ which allows us to write $-k$ on the board as well for sufficiently large positive $k$ . Then, using rule (i), we can create all integers greater than $-k$ as well which implies that we can write all integers on the board using a finite number of steps.

Now, consider a initial pair $(u,v)$ where $u>0$ . Then, we can write $k=u+v$ on the board. Further, we can also clearly write $ul+v$ for all positive integers $l$ , so consider sufficiently large $l$ such that $r=ul+v>1$ . Now, we can also write $k+r$ as it is a linear combination of $u$ and $v$ with positive integral coefficients. Then, since we can write $k$ , $r$ and $k+r$ , considering the polynomial,
$kx^2+(k+r)x+r = 0 \implies (kx+r)(x+1) =0$ which allows us to write $-1$ on the board. But now, applying rule (i) on $u$ and $-1$ we obtain $u-1$ , continuing this likewise, we can obtain $1$ . Once $1$ is written on the board, by the previous claim, we know that we can write all integers on the board which finishes the proof.