Library / /121 of 129

, 2012

Combinatorics Difficulty 6.7 National Olympiad Prove it Slovenia

A mole named Črt has 5 rooms in his lair. The rooms are numbered with numbers from 1 to 5. Črt has drilled tunnels between some of the rooms so that he can crawl from every room to any other room using some of the tunnels. No two tunnels intersect. Every tunnel starts in one room and ends in another room (different from the first one), and it does not pass through any other rooms. Rooms that are directly connected by a tunnel we call neighbouring. List all the pairs of neighbouring rooms if you know the following.

* By crawling through exactly three (not necessarily different) tunnels Črt cannot reach rooms 1 and 5 from room 5.
* By crawling through exactly two tunnels Črt can reach rooms 2 and 3 from room 5.
* By crawling through exactly three (not necessarily different) tunnels Črt can reach room 1 from room 3.

Solution

We first notice that rooms $5$ and $1$ cannot be neighbouring. If they were, Črt could reach room $1$ from room $5$ by crawling through the connecting tunnel exactly three times—first from room $5$ to room $1$ , then back to room $5$ , and then again to room $1$ . This would be in contradiction with the known facts about the rooms in the mole's lair. Similarly, room $5$ cannot be directly connected with rooms $2$ and $3$ . If room $5$ was neighbouring to room $2$ , for instance, Črt could crawl from room $5$ back to room $5$ through exactly three tunnels—first from room $5$ to room $2$ through exactly two tunnels (a fact about the lair) and then through the tunnel between rooms $2$ and $5$ back to room $5$ .

Because Črt can crawl through exactly two tunnels from room $5$ to room $2$ and because room $5$ can be directly connected only with room $4$ , the following pairs of rooms must be directly connected with tunnels: rooms $5$ and $4$ , rooms $4$ and $2$ , rooms $4$ and $3$ .

Because Črt cannot reach room $1$ from room $5$ by crawling through exactly three tunnels (a fact about the lair), room $1$ cannot be neighbouring to rooms $2$ and $3$ . If this was the case, Črt could crawl from room $5$ to room $1$ through exactly three tunnels passing rooms $4$ and $2$ or rooms $4$ and $3$ .

Because Črt can crawl through exactly three tunnels from room $3$ to room $1$ (a fact about the lair), two more pairs of rooms must be directly connected with tunnels: rooms $1$ and $4$ , rooms $2$ and $3$ .

All pairs of neighbouring rooms are thus $(1, 4)$ , $(2, 3)$ , $(2, 4)$ , $(3, 4)$ and $(4, 5)$ .

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.