The squares of a 4 x 7 chess board are colored red or blue. Show that however the coloring is done, we can find a rectangle with four distinct corner squares all the same color. Find a counter-example to show that this is not true for a 4 x 6 board.
Solution
A counter-example for 4 x 6 is:
R B R B R B R B B R B R B R R B B R B R B R R BEvery column has two blue and two red squares and no two columns have the red squares in the same two rows or the blue squares in the same two rows, so there can be no rectangles.
Suppose there is a counter-example for a 4 x 7 rectangle. Suppose it has three red squares in the first column. Then in those rows each remaining column can have at most one red square, so four remaining columns each have at least two blue squares in those three columns. Hence two of those columns have blue squares in the same two rows and hence a blue cornered rectangle. Contradiction. Similarly if there are three blue squares in the first column. So each column must have two red and two blue squares. But there are only 6 ways of choosing 2 items from 4, so two columns must have red squares in the same rows. Contradiction.
© John Scholes
jscholes@kalva.demon.co.uk
11 Jul 2002