Let $m \ge n$ be positive integers. Frieder is given $mn$ posters of Linus with different integer dimensions of $k \times l$ with $1 \ge k \ge m$ and $1 \ge l \ge n$. He must put them all up one by one 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.
Problem
Source: Switzerland Final Round 2021 P7
Tags: combinatorics
24.02.2021 15:22
I think the last two inequalities should be reversed. Assuming so, here's the solution. Denote by $(x,y)$ the poster with sides $x$ and $y$. Lemma: if $x<z$ and $y>w$ then neither of $(x,y)$ and $(z,w)$ can fit inside the other. Proof: trivial. We can now define a chain of poster as a sequence of posters each one of which under the next one. By looking at posters $(m,1),(m-1,2),...,(m-n+1,n)$, by our lemma there must be at least $n$ chains, since each of the poster can't fit inside the others. Similarly the $n-1$ posters $(m,2),(m-1,3),...,(m-n+2)$ are in different chains, so by pigeonhole at least one of the previous group must be the upper element of a chain, and so we must minimize it's area, and we notice that $\min k(m+1-k)=m$ if $1\leq k\leq n$. Similarly the $m-2$ posters $(m,3),(m-1,4),...,(m-n+3)$ must be in different chains, and at least one poster of the previous group must be an upper element of a chain and to minimize it's area we take $(m,2)$. Going on with this logic, the upper elements of the chain are $(m,1),(m,2),...,(m,n)$ (which can be achieved by taking the chains with second side constant) for a total area of $A=m\cdot 1+\cdots +m\cdot n=m\frac{n(n+1)}{2}$.
14.01.2023 14:23
Yes. In the original problem, it says $1 \le k \le m$ and $1 \le l \le n$