Cells of a 15×15 square grid have been painted in red, blue and green. Prove that there are at least two rows of cells with the same number of squares of at least one of the colors.

Solution

Assume that, for each color, each row contains a different number of cells colored with that color. Then the minimum number of cells of one color could not be less than

0 + 1 + 2 + 3 + ... + 13 + 14 = 105.

To satisfy this condition for all three colors, one needs 105×3 = 315 cells which exceeds the total number of available cells: 15×15 = 225.