Tessellate S.T.E.M.S (2019) - Mathematics - Category B - Set 3 - Subjective Problem 2

A company wants to build a 20012001 x 20012001 building with doors connecting pairs of adjacent rooms (which are 11 x 11 squares, two rooms being adjacent if they have a common edge). Is it possible for every room to have exactly 22 doors?


This problem is a part of Tessellate S.T.E.M.S. (2019)

#Combinatorics

Note by Tessellate S.T.E.M.S. Mathematics
2 years, 7 months ago

No vote yet
1 vote

  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:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

No.

Let n=2001.n=2001. Color the rooms with a checkerboard pattern. Each door separates a white room from a black room. Let DD be the total number of doors in the building. Then DD must equal the sum of the number of doors in the black rooms (since every door touches a unique black room), and DD 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 nn 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 nn is even.

Patrick Corn - 2 years, 5 months ago
×

Problem Loading...

Note Loading...

Set Loading...