Problem 6

Consider a

2025\times2025

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.

Step 6 of 6: Conclusion for n = 2025

Previous step Next step

2025+2\cdot45-3=2112

Detailed analysis

Steps 2 and 4 together show the minimum number of tiles is exactly $n+2\sqrt n-3$ whenever $n$ is a perfect square. For $n=2025=45^2$ , this equals $2025+2\cdot45-3=2112$ .