Browse · MathNet
PrintHellenic Mathematical Olympiad
Greece counting and probability
Problem
Let a square of side length cm which is divided, with lines parallel to its sides, into small squares of side cm. Color small squares black, and the other small squares are white. Suppose that there is a positive integer such that no matter which squares are black, there is a rectangle of area with sides parallel to the sides of and all of its small squares that contains are white. Find the maximum value of .
Solution
We divide into rectangles . Since we color seven small squares with black color, from pigeonhole, there will be at least one rectangle that contains no black square and of course its area is .
Figure 1
In what follows we will prove that there is a coloring with black squares, such that there is no rectangle with only white squares and area bigger than . Indeed, we can see such a coloring at the following figure.
Figure 2
Figure 1
In what follows we will prove that there is a coloring with black squares, such that there is no rectangle with only white squares and area bigger than . Indeed, we can see such a coloring at the following figure.
Figure 2
Final answer
8
Techniques
Pigeonhole principleColoring schemes, extremal arguments