Lemma › Guides › EGMO 2024 Problem 1: solution, and the three ways a pair gets stuck
Guide

EGMO 2024 Problem 1: solution, and the three ways a pair gets stuck

14 November 2026

EGMO 2024 Problem 1 looks like a hunt through an unbounded process, with a quadratic equation thrown in to make it hard to follow. It is not. There is one short trick that turns the quadratic into a way to write −1-1, a cheap way to climb from there to every integer, and three clean reasons why the other starting pairs get stuck. Here is the statement, the answer, the full proof, an independent check, and the part most write-ups skip: what in the wording points at the method.

The problem. Two different integers uu and vv are written on a board. We perform a sequence of steps. At each step we do one of the following two operations: (i) If aa and bb are different integers on the board, then we can write a+ba + b on the board, if it is not already there. (ii) If aa, bb and cc are three different integers on the board, and if an integer xx satisfies ax2+bx+c=0ax^2 + bx + c = 0, then we can write xx on the board, if it is not already there. Determine all pairs of starting numbers (u,v)(u, v) from which any integer can eventually be written on the board after a finite sequence of steps.

Answer: exactly the pairs where neither number is 00, at least one is positive, and the pair is not {−1,1}\{-1, 1\}.

The signal in the statement

Try a few pairs by hand before proving anything. {0,v}\{0, v\} goes nowhere, {−1,1}\{-1, 1\} produces only 00 and then stops, and {−3,−2}\{-3, -2\} never leaves the negatives. Everything else you try climbs without trouble.

Solution

Three families of pairs fail.

  1. A pair containing zero. The board is {0,v}\{0, v\}. The only sum of two different board numbers is 0+v=v0 + v = v, already there, and operation (ii) needs three different numbers. Nothing can ever be written.
  2. Both numbers negative. Claim: every number on the board stays negative. A sum of two negatives is negative. For a root, suppose a,b,ca, b, c are all negative and ax2+bx+c=0ax^2 + bx + c = 0 has a real root xx. Then x≥0x \ge 0 is impossible, since ax2+bx+c<0ax^2 + bx + c < 0 for x≥0x \ge 0. So xx is negative. Since 00 and the positives never appear, the board never holds every integer.
  3. The pair of minus one and one. Writing −1+1-1 + 1 puts 00 on the board, and every other sum is already there. The board is now {−1,0,1}\{-1, 0, 1\}. Operation (ii) can only use these three numbers as a,b,ca, b, c in some order, and there are six orders. Checking them, every integer root is already −1-1, 00 or 11: for example x2−1x^2 - 1 has roots ±1\pm 1, and x2−xx^2 - x has roots 00 and 11. The board is closed and never grows.

Every other pair works. Now uu and vv are nonzero, at least one is positive, and {u,v}≠{−1,1}\{u, v\} \ne \{-1, 1\}.

Step 1: write minus one. If −1-1 is not on the board yet, take a=ua = u and c=vc = v. Both are nonzero and different, so b=a+cb = a + c differs from both aa and cc, and operation (i) writes it. Now aa, bb, cc are three different board numbers and ax2+(a+c)x+c=(ax+c)(x+1)ax^2 + (a + c)x + c = (ax + c)(x + 1) has the integer root −1-1. Operation (ii) writes −1-1.

Step 2: get a positive number of at least two. If the larger of u,vu, v is already at least 22, call it pp. Otherwise the positive number is 11, the other number is ww, and w≠0w \ne 0, w≠−1w \ne -1 because the pair is not {−1,1}\{-1, 1\}, so w≤−2w \le -2.

Step 3: climb to every integer. The board has −1-1 and some p≥2p \ge 2.

  1. Add −1-1 to pp, then to p−1p - 1, and so on. Each step uses two different numbers, so the board gets p−1,p−2,…,1,0p - 1, p - 2, \ldots, 1, 0. Now 00, 11 and 22 are on it.
  2. For n≥2n \ge 2 on the board, nn and 11 are different, so n+1n + 1 is written. By induction every positive integer is on the board.
  3. For n≥2n \ge 2, the numbers 11, n+1n + 1, nn are three different board numbers and

x2+(n+1)x+n=(x+1)(x+n)x^2 + (n + 1)x + n = (x + 1)(x + n) has the root −n-n. So every negative integer is written too.

So the board eventually holds every integer.

An independent check

The build behind this page does not trust the proof. It runs the two operations to closure on a board of bounded size, starting from every pair of different integers in a small range, and confirms that the pairs that reach all of a window around 00 are exactly the pairs the answer describes. It separately confirms that closures from two negative starting numbers contain only negatives, that {0,v}\{0, v\} stays at two numbers, and that {−1,1}\{-1, 1\} stops at three. Finally it replays the construction above step by step, with every legality condition asserted, for every qualifying pair with both numbers between −40-40 and 4040, and confirms every integer from −60-60 to 6060 appears.

Where marks go missing

Practise the idea

The first half of this problem, showing a set is closed so nothing new can ever appear, is the pattern behind every invariant argument. The classic place to see it cleanly is the mutilated chessboard in the archive, where a colour count that no domino can change shows a cover is impossible. The method is written up under invariants, and the techniques index lists the other ideas that recur in olympiad problems. The daily problem posts a new one every day, no account needed.

Related guides

Train it on Lemma

Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.

Find your level