Competition problem — Combinatorics

Library / /2 of 14

Combinatorics Difficulty 5.9 AIME, harder Prove it Greece

Let a square $ABCD$ of side length $8$ cm which is divided, with lines parallel to its sides, into $64$ small squares of side $1$ cm. Color $7$ small squares black, and the other $57$ small squares are white. Suppose that there is a positive integer $k$ such that no matter which $7$ squares are black, there is a rectangle of area $k\ \text{cm}^2$ with sides parallel to the sides of $ABCD$ and all of its small squares that contains are white. Find the maximum value of $k$ .

Solution

We divide $ABCD$ into $8$ rectangles $4 \times 2$ . Since we color seven small squares with black color, from pigeonhole, there will be at least one $4 \times 2$ rectangle that contains no black square and of course its area is $8\,\text{cm}^2$ .

Figure 1

In what follows we will prove that there is a coloring with $7$ black squares, such that there is no rectangle with only white squares and area bigger than $8\,\text{cm}^2$ . Indeed, we can see such a coloring at the following figure.

Figure 2

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.