Competition problem — Combinatorics

Library / /23 of 24

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:
A building has seven rooms numbered $1$ through $7$ , 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 $1$ and the outside, and a treasure in room $7$ . 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 $1$ , 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.

Solution

Solution:
On the way to the treasure, no room need be entered twice; otherwise the path could be shortened by skipping the loop. Thus, the minimal path to the treasure, if it exists, is at most $7$ steps long. Similarly, the minimal path from the treasure to the outside is at most $7$ steps long, so the total number of steps cannot exceed $14$ . The arrangement of the rooms in a line, with $1$ and $7$ at opposite ends and two-way doors between all adjacent rooms, shows that $14$ is attainable.

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.