Berkeley Math Circle Monthly Contest 2 #0hkj
Berkeley Math Circle Monthly Contest 2Hard
From module Graph Theory (Intro)
Community difficultyNo ratings yetBe the first to rate this problem.
Understand the scale
Scale
0.5: Easiest math competition problems, often solvable even for early middle school students without experience.
1: Problems strictly for beginners, often at a moderate middle school level.
1.5: Problems for stronger beginner students, on the level of the middling problems in most middle school contests.
2: For motivated beginners, harder questions from the previous categories.
2.5: More advanced beginner problems, hardest questions from previous categories.
3: Early intermediate problems that require more creative thinking.
3.5: Tougher early intermediate problems that consistently stretch into higher-level creative thinking or conceptual knowledge.
4: Intermediate-level problems.
4.5: Upper intermediate problems approaching the upper bound for non-invitational sprint math competitions.
5: More difficult AIME problems or simple proof-based Olympiad-style problems.
6: High-level AIME-styled questions or introductory Olympiad-level questions.
7: Tougher Olympiad-level questions, may require more technical knowledge.
8: High-level Olympiad-level questions.
9: Expert Olympiad-level questions.
9.5: The hardest problems appearing on Olympiads which the strongest students could reasonably solve.
10: Historically notorious problems, generally unsuitable for even very hard competitions because they are exceedingly tedious, long, and difficult.
Graph TheoryColoring schemes, extremal arguments
Problem
Problem: A building has seven rooms numbered through , all on one floor, and any number of doors connecting these rooms. These doors may be one-way, admitting motion in only one of the two directions, or two-way. In addition, there is a two-way door between room and the outside, and a treasure in room . Your object is to choose the arrangement of the rooms and the locations of the doors in such a way that
a. it is possible to enter room , reach the treasure, and make it back outside,
b. the minimum number of steps required to do this (each step consisting of walking through a door) is as large as possible.