7. Let $m \geq n$ be positive integers. Frieder is given $m n$ posters of Linus with different integer dimensions $k \times l$ with $1 \leq k \leq m$ and $1 \leq l \leq n$. He must put them all up one by on his bedroom wall without rotating them. Every time he puts up a poster, he can either put it on an empty spot on the wall, or on a spot where it entirely covers a single visible poster and does not overlap any other visible poster. Determine the minimal area of the wall that will be covered by posters.

Remark: a wall is a structure often made of bricks and concrete (or cardboard if you live in Winterthur) commonly found in houses.

Answer: $m \frac{n(n-1)}{2}$
Solution (Tanish): We introduce the following definitions ${ }^{1}$ :

- A chain is a sequence of posters, each of which covers the previous one completely.
- An antichain is a group of posters, none of which can be placed over any of the others because it would not cover any of the others completely.
- The minimal and maximal elements in a chain are the first (smallest) and last (largest) elements in that chain, respectively.
- The degree of a poster is the sum of its length and width.

With these definitions we can note two facts already: the total area of the wall covered is the total area of the maximal elements of all chains (this is trivial), and all elements of an antichain must belong to different chains (this is because the relationship "can be placed over" is transitive: if Poster A can be placed over Poster B and Poster B can be placed over Poster C, then Poster A can be placed over poster C).

Firstly, note that the $n$ posters with dimension $m \times 1, m-1 \times 2, \ldots, m-n-1 \times n$ form an antichain (more generally, you can say all posters of a given degree $x$ form an antichain) and so we must have at least $n$ different chains. We therefore have at least $n$ maximal posters of degree $\geq m+1$. Analogously we have at least $n+1-k$ maximal posters of degree $\geq m+k$ for any $k \in\{1,2, \ldots, n\}$ (using the same argument as before with the antichain of posters of degree $m+k)$.

With this information, let us try and find a lower bound on the total area of these maximal posters (we don't know if satisfying these facts will be enough, but we can use it to give a bound and then try to attain this bound with a construction). Suppose there are no maximal elements of some degree $m+k$; the pigeonhole principle tells us there must therefore be two or more maximal posters of some degree $m+l, l>k$. However for any poster of degree $m+l$ there is always a poster of degree $m+k$ that fits inside it, and so changing one of the maximal posters of degree $m+l$ for such a poster of degree $m+k$ will strictly reduce the total area. In other words, a set of maximal posters with minimal combined area would have at least one element of degree $m+k, \forall k \in\{1,2, \ldots, n\}$. The smallest poster of degree $m+k$ is the poster $m \times k$ (once the perimeter is fixed the area is minimised by maximising the difference between height and width) and so a lower bound on the total area of the posters would be:

$$
(m+2 m+\cdots+n m)=m \frac{n(n+1)}{2}
$$

However, this bound can easily be attained: one construction would be to create chains by placing all the posters $x \times y, 1 \leq x \leq m$ on top of each other. This gives a chain for each $y \in\{1,2, \ldots, n\}$.[^0]