There is a 15 × 15 grid, each square is colored either red, blue orgreen. Prove that there are at least two rows in which the number of squares in one color is the same.
Suppose no two rows have the same number of squares of one of the colors. (This is called proof by contradition.)
So, for example, no two rows have the same number of blue squares. The options for the number of blue squares in a row is:
So we have 16 options, and 15 rows. Let's suppose that there are as few blue squares on the grid as possible. Then the rows must contain:
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14 blue squares. So, in order for each row to contain a different number of blue squares, there must be at least 0+1+2+...+13+14 = 105 blue squares on the board.
We can do this argument with green and red, as well.
In order for each row to contain a different number of green squares, there must be at least 105 green squares on the board. Similarly, we must have at least 105 red squares on the board.
Thus, for this to happen, we need at least 315 squares on the board.
But 15*15=225. There are only 225 squares on the board. Thus it can't happen that, for each color, no two rows have the same number of that color.