Tuesday, February 21, 2006

Doors, Doors, and Mores! Topic: Invariants. Level: AIME/Olympiad.

Problem: (2000-2001 Berkeley Math Circle Contest, Gabriel Carroll Original) A company wants to construct its new office building, a $2001 \times 2001$ square grid of rooms, with doors connecting pairs of adjacent rooms, so that each room has exactly two doors. Prove that this cannot be done.

Solution: Place the lower left corner at the origin. Label each room by its lower-left corner. Number the rooms in the following way - if the sum of its label ($ (x,y) \rightarrow x+y $) is even, it is $ 0 $ and if the sum of its label is odd, it is $ 1 $. We note that each door connects two rooms of opposite numbers.

Since each room has two doors, we have a total of $ 2 \cdot 2001^2 $ doors, but this counts each door twice - once from each side. So we divide by two to just get $ 2001^2 $ doors, which is odd.

The number of doors in all the rooms is also equal to the number of doors in rooms with value $ 1 $ (since each door in a $ 0 $ room will be counted by the $ 1 $ room on the other side). But if each room has exactly two doors, the total number must be even, which cannot equal the odd sum above. Contradiction.

So it is impossible to have exactly two doors in every room. QED.

--------------------

Comment: Once again, we see that the right numbering works wonders. Parity is usually a good thing to watch out for in invariant problems ("cannot be done" is a good clue).

No comments:

Post a Comment