4. Krt Črt has 6 rooms in his burrow, numbered from 1 to 6. Črt has dug tunnels between some of them, 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 other room. Rooms that are directly connected by a tunnel are called neighboring. List the pairs of neighboring rooms if the following conditions are met:

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

# 56th Mathematical Competition for High School Students in Slovenia

Koper, April 21, 2012

## Solutions to the Problems and Scoring System
IV/4. Sobi 1 in 2 nista sosednji, saj bi sicer Črt prek treh rovov lahko prišel iz sobe 1 v sobo 2 s sprehodom $1-2-1-2$. Ker lahko prek treh rovov pride v sobo 1, ne pa prek štirih rovov v sobo 6, soba 1 ne sme biti sosednja sobi 6. Ker lahko Črt prek treh rovov iz sobe 1 pride nazaj v sobo 1, morata obstajati dve različni sobi $X$ in $Y$ (različni od 1), tako da so si sobe 1, $X$ in $Y$ sosednje. Ker lahko iz sobe $1 \mathrm{v}$ sobi $X$ in $Y$ pride prek dveh rovov, nobena od teh dveh sob ni soba 5. Iz že dokazanega sledi tudi, da nobena od teh dveh sob ni soba 2 ali 6, zato sta sobi $X$ in $Y$ sobi 3 in 4. Pokazali smo torej, da so si sobe 1, 3 in 4 sosednje. Soba 3 ni sosednja sobi 5, saj bi sicer Črt lahko prek dveh rovov prišel iz sobe $1 \mathrm{v}$ sobo 5 s sprehodom $1-3-5$. Podobno soba 4 ni sosednja sobi 5. Soba 3 ni sosednja sobi 2, saj bi sicer Črt lahko prek treh rovov prišel iz sobe $1 \mathrm{v}$ sobo $2 \mathrm{~s}$ sprehodom $1-4-3-2$. Podobno soba 4 ni sosednja sobi 2. Soba 3 ni sosednja sobi 6, saj bi sicer Črt lahko prek štirih rovov prišel iz sobe $1 \mathrm{v}$ sobo $6 \mathrm{~s}$ sprehodom $1-3-1-3-6$. Podobno soba $4 \mathrm{ni}$ sosednja sobi 6. Edini preostali možen sprehod iz sobe $1 \mathrm{v}$ sobo 6 prek treh rovov je sprehod $1-5-2-6$, torej sta sobi 1 in 5 sosednji, sobi 5 in 2 sosednji ter sobi 2 in 6 sosednji. Sobi 5 in 6 nista sosednji, saj bi sicer Črt lahko prek štirih rovov prišel iz sobe 1 v sobo $6 \mathrm{~s}$ sprehodom $1-5-1-5-6$. Pari sosednjih sob so torej pari $(1,3),(1,4),(1,5),(2,5),(2,6)$ in $(3,4)$.
![](https://cdn.mathpix.com/cropped/2024_06_07_550bffe3dbbdd9dbd37bg-15.jpg?height=408&width=1360&top_left_y=521&top_left_x=356)

#### Abstract

Conclusion that rooms 1 and 2 are not adjacent 1 point

Conclusion that rooms 1 and 6 are not adjacent 1 point

Conclusion that rooms 1, 3, and 4 are adjacent 1 point

Conclusion that rooms 3 and 4 are not adjacent to rooms 2, 5, and 6 2 points

Conclusion that room 1 is adjacent to 5, room 5 is adjacent to 2, and room 2 is adjacent to 6 1 point

Conclusion that rooms 5 and 6 are not adjacent 1 point

If the reasoning is missing in several conclusions, 1 point is deducted. If the contestant writes the correct solution without all the reasoning, they get 3 points.

2. method. From the first condition, it follows that there exist different rooms $X \neq 1$ and $Y \neq 1$ such that rooms 1, $X$, and $Y$ are adjacent. Similarly, there exist different rooms $Z \neq 1$ and $W \neq 6$ such that room 1 is adjacent to $Z$, $Z$ is adjacent to $W$, and $W$ is adjacent to 6. Room 6 is not adjacent to room 1, otherwise we would have a path $1-X-Y-1-6$. Therefore, $X, Y, Z \neq 6$ and $W \neq 1$. If $Z = X$, we would have a path $1-Y-X-W-6$, which is not possible. Therefore, $Z \neq X$ and similarly $Z \neq Y$. If $W = X$, we would have a path $1-X-1-X-6$, which is also not possible. Therefore, $W \neq X$ and similarly $W \neq Y$. We have shown that rooms $1, 6, X, Y, Z$, and $W$ are different. Since there are 6 rooms in total, these are exactly all the rooms. From the second condition, it follows that room 2 is not adjacent to room 1, otherwise we would have a path $1-2-1-2$. Therefore, $2 \neq X, Y, Z$ and thus $2 = W$. Since we can reach rooms $X$ and $Y$ from room 1 in two tunnels, it follows that $5 = Z$. Rooms $X$ and $Y$ are therefore rooms 3 and 4 (due to symmetry, it doesn't matter which is which). Similarly as in the first solution, we show that there are no other adjacencies between the rooms. The pairs of adjacent rooms are therefore exactly the pairs $(1,3),(1,4),(1,5),(2,5),(2,6)$, and $(3,4)$.

Conclusion that rooms 1 and 6 are not adjacent 1 point

Proof that rooms $1, 6, X, Y, Z, W$ are different 3 points

Determination of the values of rooms $X, Y, Z, W$ 2 points

Proof that there are no other adjacencies between the rooms 1 point

If the reasoning is missing in several conclusions, 1 point is deducted. If the contestant writes the correct solution without all the reasoning, they get 3 points.