Imagine an array of 3 x 7 lights. Lights can be on or off. Show that no matter which lights you turn on or off, you will always be able to find four lights forming the corner of a rectangle, either all on or all off.

Let assign 3 columns and 7 rows.  Each row must have a pair that match (or perhaps all 3 match).  Consequently, if any row is duplicated, there will be a rectangle of 4 matching lights.  Consider the two following cases. 

Case 1: If any row has all three bulbs in the same state, then none other rows could have any two bulbs of that state without giving you the rectangle.  This only leaves only 4 possibilities for the remaining 6 rows.  Since some repetition of rows will be required, this will inevitably give the rectangle of 4 matching lights.

Case 2: If no row has all three bulbs in the same state, then there are only 2^3-2 or 6 posibile rows.  To fill the last row, something will have to be repeated giving the rectangle of 4 matching lights. 

Thus there will always be a rectangle of 4 matching lights.

Posted by stan on 2004-09-14 13:29:44