A company wants to build a x building with doors connecting pairs of adjacent rooms (which are x squares, two rooms being adjacent if they have a common edge). Is it possible for every room to have exactly doors?
This problem is a part of Tessellate S.T.E.M.S. (2019)
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
No.
Let n=2001. Color the rooms with a checkerboard pattern. Each door separates a white room from a black room. Let D be the total number of doors in the building. Then D must equal the sum of the number of doors in the black rooms (since every door touches a unique black room), and D must also equal the sum of the number of doors in the white rooms (since every door touches a unique white room). If every room has exactly two doors, this implies that the number of black rooms and white rooms must be equal; but since n is odd this is impossible.
In the language of graph theory, adapting this argument shows that in a regular bipartite graph, the sizes of the two parts must be equal. The graph with the rooms as vertices and edges appearing if rooms are connected by a door is bipartite (white rooms and black rooms), so the only way it can be regular is if the numbers of rooms are equal, which only happens if n is even.