IMO 2025 · Problem 6

Consider a \(2025 \times 2025\) grid of unit squares. Matilda wishes to place on the grid some rectangular tiles, possibly of different sizes, such that each side of every tile lies on a grid line and every unit square is covered by at most one tile.

Determine the minimum number of tiles Matilda needs to place so that each row and each column of the grid has exactly one unit square that is not covered by any tile.

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{2112} \]

Solution

Call the uncovered unit squares holes. We first prove that on an \(n\times n\) board, any valid arrangement uses at least \[ n+2\sqrt n-3 \] tiles. We then attain this bound when \(n=2025=45^2\).

Lower bound.

Suppose there are \(t\) tiles. Regard the \(n\) holes as additional \(1\times1\) rectangles, obtaining a partition of the whole board into \(t+n\) rectangles.

Let \(s\) be the total number of maximal straight segments formed by the internal boundaries of this partition. Segments continue through junctions whenever the boundary continues straight. Let \(x\) be the number of interior junctions at which four rectangles meet.

We claim that \[ t+n=1+s+x. \tag{1} \] Indeed, let \(u\) be the number of interior T-junctions, and let \(b\) be the number of boundary junctions other than the board’s four corners. Each T-junction or boundary junction is the endpoint of exactly one maximal internal segment, whereas a four-way junction is not an endpoint. Thus \[ 2s=u+b. \] Counting corners of the \(t+n\) rectangles gives \[ 4(t+n)=4+2u+2b+4x, \] which proves (1). These counts also apply when holes touch the boundary or meet diagonally.

Number the rows from bottom to top and the columns from left to right. The hole in row \(r\) lies in some column \(p(r)\), where \(p\) is a permutation of \(1,\ldots,n\).

For each pair of consecutive rows, draw a horizontal bridge joining the midpoints of the two hole sides lying on their common row boundary. Similarly, for each pair of consecutive columns, draw a vertical bridge joining the midpoints of the two hole sides on their common column boundary.

Initially retain precisely those bridges that lie entirely on boundaries of the rectangle partition. If a horizontal bridge is not retained, its two endpoint hole sides belong to different maximal horizontal boundary segments. Hence that horizontal grid line contains at least two such segments. Every internal horizontal grid line contains at least one segment, and the analogous statements hold vertically. Consequently, the number of bridges not retained is at most \[ s-2(n-1). \]

Whenever a retained horizontal bridge intersects a retained vertical bridge, their intersection is a four-way junction: it lies in the interior of both bridges, since bridge endpoints are side midpoints whereas such intersections are grid vertices. There are therefore at most \(x\) such intersections.

Delete every retained horizontal bridge that intersects a retained vertical bridge. This deletes at most \(x\) further bridges. We now have no intersections between retained horizontal and vertical bridges, and the total number of omitted bridges is at most \[ s-2(n-1)+x=t-n+1, \tag{2} \] using (1).

The retained horizontal bridges divide the rows into \(h\) consecutive blocks: two consecutive rows belong to the same block exactly when their bridge was retained. Likewise, the retained vertical bridges divide the columns into \(v\) consecutive blocks. The total number of omitted bridges is \[ (h-1)+(v-1). \] Thus (2) gives \[ h+v\le t-n+3. \tag{3} \]

We next show that each intersection of a row block and a column block contains at most one hole.

For a fixed row block, draw the vertical unit segment through the centre of every hole in that block, and join these segments using the retained horizontal bridges. Extend the bottom and top ends vertically to infinity, producing a path \(P\). Every horizontal line meets \(P\) in either one point or one segment. Thus every point outside \(P\) lies unambiguously to its left or to its right, and this designation cannot change continuously without meeting \(P\).

For a fixed column block, construct the analogous path \(Q\) from horizontal unit segments through its holes and retained vertical bridges. Extend its ends horizontally to infinity, and traverse it from left to right.

The horizontal parts of \(P\) cannot intersect the vertical parts of \(Q\), because these are retained bridges. Parallel parts cannot meet either: vertical parts of \(P\) have half-integer horizontal coordinates, while vertical parts of \(Q\) have integer horizontal coordinates; the analogous distinction holds for horizontal parts.

Therefore every intersection of \(P\) and \(Q\) has \(P\) vertical and \(Q\) horizontal. At each such intersection, \(Q\) crosses from the left side of \(P\) to its right side. There can be at most one such crossing, since a second would require an intervening return to the left side. Every hole belonging to both chosen blocks contributes an intersection at its centre. This proves the claim.

There are \(hv\) block intersections and \(n\) holes, so \[ n\le hv. \] Combining this with (3) and the arithmetic–geometric mean inequality yields \[ t-n+3\ge h+v\ge2\sqrt{hv}\ge2\sqrt n. \] For \(n=2025\), this gives \[ t\ge2025+90-3=2112. \tag{4} \]

Construction attaining the bound.

Let \(m=45\), \(n=m^2=2025\), and \(N=m^2+1=2026\). We describe a pattern on the infinite grid and then restrict it to the board.

For every pair of integers \((a,b)\) satisfying \[ b\equiv ma\pmod N, \] take the \(m\times m\) square consisting of rows \[ a+1,\ldots,a+m \] and columns \[ b,\ldots,b+m-1. \]

These squares cover exactly once every unit square \((r,c)\) for which \[ c\not\equiv mr\pmod N, \] and leave all other unit squares uncovered. To verify this, a unit square in the square indexed by \((a,b)\) has \[ r=a+u,\qquad c=b+w, \] where \(1\le u\le m\) and \(0\le w\le m-1\). Hence \[ mr-c\equiv mu-w\pmod N. \] The numbers \(mu-w\), as \((u,w)\) varies over these ranges, are precisely \(1,2,\ldots,m^2\), each once.

Thus a cell with residue \(0\) is uncovered. For any other cell, its residue uniquely determines \(u,w\), and then uniquely determines \[ a=r-u,\qquad b=c-w. \] This proves both coverage and nonoverlap.

Intersect these squares with the \(n\times n\) board, keeping only positive-area intersections. Each intersection is a valid rectangular tile. The holes are precisely the cells satisfying \[ c\equiv mr\pmod N. \] Since \(\gcd(m,N)=1\), multiplication by \(m\) permutes the nonzero residues modulo \(N\). Therefore there is exactly one hole in every row and column of the board.

It remains to count the tiles. The square indexed by \((a,b)\) meets the board in positive area exactly when \[ 1-m\le a\le n-1, \qquad 2-m\le b\le n. \] The admissible pairs satisfying \(b\equiv ma\pmod N\) fall into three cases:

  • If \(a\ge1\) and \(b\ge1\), each \(a=1,\ldots,n-1\) gives exactly one \(b\in\{1,\ldots,n\}\). This gives \(n-1\) tiles.
  • If \(a<0\), write \(a=-k\), where \(1\le k\le m-1\). The unique admissible value is \(b=N-mk>0\), giving \(m-1\) tiles. Indeed, the next smaller congruent value is \(-mk<2-m\).
  • If \(a\ge0\) and \(b\le0\), write \(b=-\ell\), where \(0\le\ell\le m-2\). Since \(m^2\equiv-1\pmod N\), the congruence gives \(a\equiv m\ell\pmod N\). Its unique admissible value is \(a=m\ell\), giving another \(m-1\) tiles.

There is no admissible pair with \(a=0\) and \(b>0\), so these cases are exhaustive. The number of tiles is therefore \[ (n-1)+(m-1)+(m-1) =n+2m-3 =2025+90-3 =\boxed{2112}. \] Together with (4), this proves minimality.

The solution was checked against the official IMO shortlist solutions.