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 , 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.
Answer: exactly the pairs where neither number is , at least one is positive, and the pair is not .
The signal in the statement
- "Determine all pairs ... from which any integer can be written." This asks which starting positions reach everything. The usual shape of the answer is "everything except a few named obstructions", so split the work in two: show the obstructions really are stuck, then show nothing else is.
- Operations that only ever add things. Nothing is ever erased, so the board only grows, and "stuck" means the board has reached a set that is closed under both operations. A closed set is exactly what an invariant describes: a property that every new number inherits from the old ones. Look for one in the small cases first.
- A quadratic with a free choice of coefficients. You choose which three board numbers play , , . When you can choose the coefficients, choose them so the polynomial factors. The sum operation hands you for free, and factors as , which has the root whatever and are. That is the whole trick.
Try a few pairs by hand before proving anything. goes nowhere, produces only and then stops, and never leaves the negatives. Everything else you try climbs without trouble.
Solution
Three families of pairs fail.
- A pair containing zero. The board is . The only sum of two different board numbers is , already there, and operation (ii) needs three different numbers. Nothing can ever be written.
- Both numbers negative. Claim: every number on the board stays negative. A sum of two negatives is negative. For a root, suppose are all negative and has a real root . Then is impossible, since for . So is negative. Since and the positives never appear, the board never holds every integer.
- The pair of minus one and one. Writing puts on the board, and every other sum is already there. The board is now . Operation (ii) can only use these three numbers as in some order, and there are six orders. Checking them, every integer root is already , or : for example has roots , and has roots and . The board is closed and never grows.
Every other pair works. Now and are nonzero, at least one is positive, and .
Step 1: write minus one. If is not on the board yet, take and . Both are nonzero and different, so differs from both and , and operation (i) writes it. Now , , are three different board numbers and has the integer root . Operation (ii) writes .
Step 2: get a positive number of at least two. If the larger of is already at least , call it . Otherwise the positive number is , the other number is , and , because the pair is not , so .
- Add to repeatedly, which operation (i) allows since each number differs from . This puts every integer from up to on the board, including and .
- Now , , are three different board numbers and has the root . Operation (ii) writes it, so take .
Step 3: climb to every integer. The board has and some .
- Add to , then to , and so on. Each step uses two different numbers, so the board gets . Now , and are on it.
- For on the board, and are different, so is written. By induction every positive integer is on the board.
- For , the numbers , , are three different board numbers and
has the root . 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 are exactly the pairs the answer describes. It separately confirms that closures from two negative starting numbers contain only negatives, that stays at two numbers, and that 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 and , and confirms every integer from to appears.
Where marks go missing
- Forgetting zero. A pair containing is the cheapest obstruction and the easiest to leave out. Say why nothing happens: the sum is already there and there are not three numbers.
- Treating "both negative" as obvious. The claim that a root of a polynomial with negative coefficients is negative needs a sentence. The one above is enough: for every term is at most zero and the constant term is not zero.
- Missing the pair of minus one and one. It is the one pair that satisfies "nonzero, one positive" and still fails. A solution that only splits on signs will claim it works.
- Skipping the distinctness checks. Operation (ii) needs three different numbers. For the trick you must say differs from and from , which is why and must be nonzero.
- Not handling a larger number of exactly one. If the larger number is you do not yet have a number at least to climb from. Without step 2 this case is a gap.
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
- What separates a Level 5 problem from a Level 7, side by sideTwo IMO inequalities, both rated 5 out of 6, sit two rungs apart on the ladder. What actually separates a Level 5 problem from a Level 7, and how to cross.
- How to prove something is impossible in a competitionFailing to find an example is not a proof that none exists. The five obstructions that rule out every attempt at once, ordered by what they cost you.
- Coloring arguments: how to know which coloring to useA coloring argument is only as good as the coloring. The signals that a combinatorics problem wants one, and how the piece decides the palette.
- When to use an invariant in a competition problemAn invariant proves impossibility, not possibility. The four signals that a problem wants one, the ladder of candidates to test, and the one-move test.
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