Lemma › Guides › EGMO 2026 Problem 1: solution, and four rectangles that isolate a cell
Guide

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.

The problem. A 2026×20262026 \times 2026 board is said to be bordeaux if at least one of its 202622026^2 unit cells is coloured red. A rectangular region made of cells is oddly-rectangular if it contains an odd number of red cells. Determine the largest positive integer MM such that, in every possible 2026×20262026 \times 2026 bordeaux board, there exists an oddly-rectangular region of at least MM cells. Note: a rectangular region has sides that are parallel to the sides of the board and contains all of its interior.

Answer: M=10132=1026169M = 1013^2 = 1026169, a quarter of the board.

The signal in the statement

Three things in the wording tell you where to look.

The single idea that makes the lower bound work is the one behind two-dimensional prefix sums. If P(x,y)P(x, y) counts the red cells in the corner rectangle [1,x]×[1,y][1, x] \times [1, y], then

P(x,y)−P(x−1,y)−P(x,y−1)+P(x−1,y−1)P(x, y) - P(x-1, y) - P(x, y-1) + P(x-1, y-1)

counts exactly the cell (x,y)(x, y). 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 22.

Solution

The construction, which shows M≤10132M \le 1013^2.

  1. Colour exactly the four central cells red: the 2×22 \times 2 block where the board's centre point is.
  2. A rectangle meets that block in a sub-rectangle of the block, so it contains 00, 11, 22 or 44 red cells. Three is impossible.
  3. 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.
  4. Each quadrant is 1013×10131013 \times 1013, so every oddly-rectangular region on this board has at most 101321013^2 cells. Hence M≤10132M \le 1013^2.

The bound, which shows M≥10132M \ge 1013^2.

  1. Suppose, for contradiction, that some bordeaux board has every rectangle of at least 101321013^2 cells containing an even number of red cells.
  2. Take any cell. By symmetry we may assume it is in the quadrant farthest from the corner (1,1)(1, 1), so it is (x,y)(x, y) with x,y≥1014x, y \ge 1014. (For a cell in another quadrant, anchor the rectangles below at the opposite corner instead.)
  3. Consider the four corner rectangles [1,x]×[1,y][1, x] \times [1, y], [1,x−1]×[1,y][1, x-1] \times [1, y], [1,x]×[1,y−1][1, x] \times [1, y-1] and [1,x−1]×[1,y−1][1, x-1] \times [1, y-1]. The smallest has (x−1)(y−1)≥10132(x-1)(y-1) \ge 1013^2 cells, so all four contain an even number of red cells.
  4. Every cell other than (x,y)(x, y) lies in an even number of these four rectangles (four, two, or none), while (x,y)(x, y) 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 (x,y)(x, y) red". So (x,y)(x, y) is not red.
  5. 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 101321013^2 cells.

The two halves meet, so M=10132M = 1013^2.

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.

  1. Assume again that every rectangle of at least 101321013^2 cells holds an even number of red cells.
  2. For a column k≥1014k \ge 1014, the regions made of columns 11 to kk and of columns 11 to k−1k-1 both have at least 2026⋅10132026 \cdot 1013 cells, so both counts are even, and their difference, column kk 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.
  3. 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.
  4. Call that corner rectangle RR. Extending the sides of RR 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, 101321013^2 cells. Contradiction.

The build behind this page brute-forces the small cases instead of trusting either proof: on a 4×44 \times 4 board it runs through every non-empty colouring and confirms that the answer is 4=224 = 2^2, a quarter of the board, exactly as the formula predicts.

Where marks go missing

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

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