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.

This is what i did.

1. There are eight possible combinations: that the rows of 3 can be in.

2. If you use one combination more than once, you automatically create the rectangle.

3. So each 3 light row would have to be different. 8 combinations - 7 rows = 1 combination that can be taken out.

4. O = on, x = off; OOO-OxO and xxx-xOx pairs make the rectangle corners, removing any of the combinations other than these, leaves both pairs to make a rectangle, elemination one of them leaves the OTHER pair to make the rectangle.

 

Posted by gabbo on 2004-09-15 22:58:33