EGMO 2026 Problem 1: solution, and four rectangles that isolate a cell
29 October 2026
EGMO 2026 Problem 1 reads like a question about colourings and is really a question about how a single cell can be written in terms of big rectangles. Here is the statement, the answer, a full proof of both halves, a second proof you can use as a check, and the part most write-ups skip: what in the wording points at the method.
Answer: , a quarter of the board.
The signal in the statement
Three things in the wording tell you where to look.
- "Largest M such that in every board there exists." This is a max-min question, so the answer has two halves that must meet: a board on which no large odd rectangle exists, and a proof that every board has one at least that large. Write both down as separate goals before doing anything else.
- "An odd number of red cells." Parity of a count is addition mod , and addition behaves well under inclusion and exclusion. Any time a condition is "the count in this region is even", try adding and subtracting regions until everything cancels except one cell.
- A board of even side. , so the board has an exact centre point where four cells meet. A symmetric construction usually lives there, and the natural guess for the answer is the area of one quadrant.
The single idea that makes the lower bound work is the one behind two-dimensional prefix sums. If counts the red cells in the corner rectangle , then
counts exactly the cell . Four big rectangles, one cell. That is a piece of double counting: each other cell is counted an even number of times, so it drops out mod .
Solution
The construction, which shows .
- Colour exactly the four central cells red: the block where the board's centre point is.
- A rectangle meets that block in a sub-rectangle of the block, so it contains , , or red cells. Three is impossible.
- So a rectangle is oddly-rectangular only when it contains exactly one of the four central cells. Then the board's centre point is one of its corners, and the rectangle lies inside one quadrant.
- Each quadrant is , so every oddly-rectangular region on this board has at most cells. Hence .
The bound, which shows .
- Suppose, for contradiction, that some bordeaux board has every rectangle of at least cells containing an even number of red cells.
- Take any cell. By symmetry we may assume it is in the quadrant farthest from the corner , so it is with . (For a cell in another quadrant, anchor the rectangles below at the opposite corner instead.)
- Consider the four corner rectangles , , and . The smallest has cells, so all four contain an even number of red cells.
- Every cell other than lies in an even number of these four rectangles (four, two, or none), while lies in exactly one of them. Adding the four red counts, which are all even, therefore gives an even total that has the same parity as "is red". So is not red.
- The cell was arbitrary, so no cell is red. That contradicts the board being bordeaux. Hence every bordeaux board has an oddly-rectangular region of at least cells.
The two halves meet, so .
A second proof of the bound, by rows and columns
This route gets to the same contradiction without the corner trick, and it is a good check on the first.
- Assume again that every rectangle of at least cells holds an even number of red cells.
- For a column , the regions made of columns to and of columns to both have at least cells, so both counts are even, and their difference, column alone, is even. Running the same argument from the other side covers the remaining columns, and the same again covers every row. So every row and every column holds an even number of red cells.
- Pick a red cell. Its row and its column together hold an odd number of red cells (even plus even, minus the red cell counted twice). The whole board is a union of rows, so it is even. So the four rectangles left when you delete that row and column, one in each corner of the board, hold an odd number of red cells between them, and at least one of them is oddly-rectangular.
- Call that corner rectangle . Extending the sides of cuts the board into four rectangles, and any two neighbours among them together form full rows or full columns, which are even. So all four have the same parity and all four are odd. They cover the board, so one has at least a quarter of it, cells. Contradiction.
The build behind this page brute-forces the small cases instead of trusting either proof: on a board it runs through every non-empty colouring and confirms that the answer is , a quarter of the board, exactly as the formula predicts.
Where marks go missing
- Proving only one half. A construction alone shows ; the parity argument alone shows . "Determine the largest" needs both, stated as such.
- Forgetting three. In the construction it is not enough to look at rectangles with one red cell. An odd count could also be three, and you need the sentence explaining why a rectangle cannot cut the block in three cells.
- Anchoring at the wrong corner. The four corner rectangles are only large enough when the cell is far from the corner they share. Say which corner you use for which quadrant, and check that the smallest of the four still has at least cells.
- Answering with the side length. The question asks for a number of cells. The quadrant has side and area , and only the area answers it.
Practise the idea
The parity move here, count something twice and let everything with an even multiplicity vanish, is the same one that proves the handshake lemma in the archive; if that proof feels automatic, the bound above will too. The method is written up in full under double counting, and the techniques index lists the other ideas that recur in olympiad combinatorics. The daily problem posts a new one every day, no account needed.
Related guides
- How to build a problem-solving notebook that actually worksMost problem notebooks are copied solutions nobody reopens. Index yours by the clue in the statement, not by topic, and test it from the clue side.
- Constructive vs complementary counting: which one to reach forTwo ways to count the same set, and one question that tells you which is cheaper. The signals, the worked pair, and the trap where the obvious tell lies to you.
- How a double counting proof is actually builtDouble counting proofs are always the same three steps, and only one of them is hard. The skeleton, five worked examples, and where they go wrong.
- Extremal graph problems for beginners: the bound and the exampleAn extremal graph problem is two problems: a bound nobody can beat and an example that reaches it. How to spot one, and which vertex to pick first.
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