Problem

Source: Ukrainian Mathematical Olympiad 2024. Day 1, Problem 9.2

Tags: combinatorics, grid, covering



For some positive integer $n$, consider the board $n\times n$. On this board you can put any rectangles with sides along the sides of the grid. What is the smallest number of such rectangles that must be placed so that all the cells of the board are covered by distinct numbers of rectangles (possibly $0$)? The rectangles are allowed to have the same sizes. Proposed by Anton Trygub