prove that the board contains a nontrivial rectangle whose 4 corner squares are all black or all red??

Question

the question is, A 3 x 7 rectangle is divided into 21 squares each of which is coloured red or black. prove that the board contains a nontrivial rectangle (not 1 x k or k) whose 4 corner squares are all black or all red

I assume this is related to pigeon hole hypothesis?? I usually panic when I get this type of problem.. I have no idea how to solve this problem.. Even though this is just a practice question, it might be on the quiz next week, so I need to understand step by step how to solve this problem.. Anyone can give me with step by step explanations?? Thanks a lot

Answer 1

Hint. See if you can explain why the following statements are true. (I assume the rectangle has $3$ rows and $7$ columns, if not then swap rows and columns in the following.)

• The rectangle must include four columns, each having two or more squares of the same colour. Call this the "majority" colour.
• Of these four columns, there must be two which have the majority colour in the same two places.
• Therefore, there is a rectangle whose four corners are the majority colour.