Problem

Source: Switzerland Final Round 2021 P7

Tags: combinatorics



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.