Library / /23 of 25

, 2008

Combinatorics Difficulty 7.0 National olympiad, round 2 Prove it Ukraine

Take the chequered board $10 \times 10$ and consider all the possible patterns of painting 10 sectors so that there is only one painted sector in every row and every column. For each pattern we find rectangle of maximal area the sides of which are on the lines of the grid. Besides, this rectangle must have no painted sectors. What can be the maximal area of such a rectangle?

Answer: 25.

Solution

Let's consider rectangles with their sides along the grid lines.
On the board let there be a rectangle with dimensions $A \times B$ , which has no painted sectors ( $A$ is its width, $B$ is its height). According to the problem statement $A$ columns which the rectangle occupies must have $A$ painted sectors. On the other hand, these $A$ sectors can not be in those $B$ rows that the rectangle occupies. The rest is $(10-B)$ rows. The obligatory condition is $10-B \ge A$ (otherwise we are not able to place $A$ painted sectors in $(10-B)$ rows, one at a row). $A+B \le 10$ (you'll obtain the same result if you consider $B$ rows). Thus rectangle $5 \times 5$ has the maximal area (this area $A(10-A) \le (\frac{A+10-A}{2})^2 = 25$ is represented in the Cauchy inequality or as a parabola with its branches down). We can easily draw an example of the board with such a rectangle (fig.3).

Fig.3

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.