4. Krt Črt has 5 rooms in his burrow, numbered from 1 to 5. Between some of them, Črt has dug tunnels, so from each room he can slide through several tunnels to any other room. No two tunnels intersect. Each tunnel starts in one room, ends in another (different from the starting one), and does not pass through any room in between. Rooms that a tunnel directly connects are called adjacent. List the pairs of adjacent rooms if the following conditions are met:

- if Črt slides through exactly three (not necessarily distinct) tunnels, he cannot get from room 5 to room 1 or 5;
- if Črt slides through exactly two tunnels, he can get from room 5 to room 2 and 3;
- if Črt slides through exactly three (not necessarily distinct) tunnels, he can get from room 3 to room 1.


## 56th Mathematical Competition for High School Students in Slovenia

Koper, April 21, 2012

## Problems for 4th Year

Solve the problems independently. You have 210 minutes to solve them. The use of notes, literature, or a pocket calculator is not allowed.
III/4. Room 5 is not adjacent to room 1, since Črt could otherwise walk from room 5 to room 1 three times, first from room 5 to room 1, then back to room 5, and then again to room 1. This would mean he would reach room 1 from room 5 in exactly three tunnels, which contradicts the problem statement. Room 5 is also not directly connected to rooms 2 and 3. If it were directly connected to room 2, for example, Črt could slide from room 5 back to room 5 in exactly three tunnels, by sliding from room 5 to room 2 in exactly two tunnels and then directly from room 2 to room 5. Since Črt can slide from room 5 to room 2 in exactly two tunnels and room 5 can only be adjacent to room 4, the pairs of rooms that must be directly connected are 5 and 4, 4 and 2, and 4 and 3. Since Črt cannot slide from room 5 to room 1 in exactly three tunnels, room 1 cannot be adjacent to rooms 2 and 3. Otherwise, Črt could slide from room 5 to room 1 via rooms 4 and 2 or 4 and 3. Since Črt can slide from room 3 to room 1 in exactly three tunnels, the pairs of rooms 1 and 4, and 2 and 3 must also be adjacent. Therefore, all adjacent pairs of rooms are $(1,4),(2,3),(2,4),(3,4)$, and $(4,5)$.
![](https://cdn.mathpix.com/cropped/2024_06_07_550bffe3dbbdd9dbd37bg-12.jpg?height=378&width=1396&top_left_y=1064&top_left_x=340)

Conclusion that rooms 5 and 1 are not adjacent

1 point

Conclusion that room 5 is not directly connected to rooms 2 and 3

2 points

Conclusion that the pairs of rooms $(2,4),(3,4)$, and $(4,5)$ are adjacent

1 point

Conclusion that room 1 is not directly connected to 2 and 3

2 points

Conclusion that the pairs of rooms $(1,4)$ and $(2,3)$ are adjacent

1 point

For each conclusion worth 2 points that is not properly justified, the contestant receives only 1 point for that conclusion. If the adjacency of the points is not addressed at all for these two conclusions, the contestant receives no points. Specifically, if the contestant writes that 5 is not adjacent to 2 or 3 because Črt can slide from 5 to 2 or 3 in exactly two tunnels, the contestant receives no points for that conclusion. If a conclusion worth 1 point is not justified, the contestant does not receive points for it. All correct pairs of adjacent rooms without justification are worth 3 points. If the contestant finds all pairs of adjacent rooms but all their conclusions are incorrect, their score is determined according to the above point system. If this score is less than 3, the contestant still receives 3 points.