Maths Olympiad Prep

Library / /48 of 105

Combinatorics Difficulty 4.9 AIME Prove it United States

Problem:

The UC Berkeley math department is about to move into a new, one-story building consisting of a 2001×20012001 \times 2001 square grid of rooms. They would like to install doors between adjacent rooms so that each room has exactly two doors. Prove that this cannot be done.

Solution

Solution:

Suppose that it can be done. Color the building in checkerboard fashion, and suppose that we obtain aa white rooms and bb black rooms. Each door connects a white room with a black room. So, if we consider, for each white room, the number of doors adjoining it, we will count each door exactly once. Since every room is to have 2 doors, the total number of doors will be 2a2a by this count. But similarly, if we consider, for each black room, the number of adjoining doors, each door will be counted once, so that the total number of doors is also equal to 2b2b. So, 2a=2b2a = 2b, or a=ba = b. It follows that the total number of rooms is a+b=2aa + b = 2a, an even number. But we also know the number of rooms is 200122001^2, an odd number - contradiction. Hence, the desired condition cannot be met.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.