B3. In the 3rd level of the computer game Treasure, the player moves through an underground dungeon, which is composed of 10 pentagonal and 8 quadrilateral rooms. The only entrance and exit to the dungeon is in one of the quadrilateral rooms, and in the remaining 17 rooms, there is one gold coin (see the image). There is a passage between every two rooms, which closes immediately when the player steps through it. When the player exits a room where they have collected a gold coin, a new gold coin appears in that room. If the player gets trapped in the dungeon, they lose all the collected coins, and the game resets. What is the maximum number of gold coins the player can bring out of the dungeon?

![](https://cdn.mathpix.com/cropped/2024_06_07_95af3fbbcea2fb458cf3g-04.jpg?height=497&width=662&top_left_y=1902&top_left_x=1254)
67th Mathematical Competition for High School Students in Slovenia National Competition, April 22, 2023

# Tasks for 4th Year 

Time for solving: 180 minutes. Each task in section A has exactly one correct answer. In section A, we will award two points for the correct answer, and deduct one point for an incorrect answer. Write the answers for section A in the left column of the answer sheet, and leave the right column blank. The committee will consider only what is written on the answer sheets, marked with the contestant's code.
B3. We observe that the 4 corner rooms have 3 doors each, and each of the remaining 13 rooms with a coin has 4 doors. A player can go through a room with 4 doors twice, thus collecting 2 coins. Through a room with 3 doors, a player can go only once, as they would otherwise be trapped in it, thus collecting 1 coin. Therefore, a player could collect a maximum of \(13 \cdot 2 + 4 \cdot 1 = 30\) coins. However, if we examine the situation more closely, we find that the player cannot collect 30 coins. Suppose the player has already completed their path through the maze and collected the coins. Let's look at the 3 rooms adjacent to the upper left corner room. Since the player has gone through this corner room at most once, there are doors in this room that the player has not used. These doors are also doors of one of the 3 adjacent rooms. Let's denote this room as A. Therefore, the player has gone through at most 3 doors of room A, which means they have gone through room A at most once. In room A, the player has thus collected at most 1 coin, even though this room has 4 doors. We can make a similar conclusion for the 3 rooms adjacent to the lower right corner room. We have thus found that among the 6 rooms marked on the left image, there are at least 2 rooms through which the player has gone at most once and in each collected at most 1 coin, even though these two rooms have 4 doors each. Therefore, instead of 30 coins, the player can collect a maximum of 28 coins. How the player can bring 28 coins from the maze is shown in the right image.
![](https://cdn.mathpix.com/cropped/2024_06_07_95af3fbbcea2fb458cf3g-14.jpg?height=504&width=1472&top_left_y=1755&top_left_x=307)

Note. Of course, the same conclusion applies to the upper right and lower left corner rooms. However, this does not reduce the maximum number of collected coins, as the left corner rooms share a common adjacent room (middle left) and the right corner rooms share a common adjacent room (middle right). This tells us that any path through the maze that allows the player to collect 28 coins must go through the middle left and middle right rooms only once and skip exactly both doors on the left edge of the maze and both doors on the right edge of the maze. This insight helps us find the appropriate path through the maze.

2. method. To show that the player can bring a maximum of 28 coins from the maze, we can also count the doors. There are 34 doors in the maze. Since each corner room has 3 doors, the player can go through it at most once. Therefore, in each corner room, there are doors that the player has not used on their path. The player has thus gone through at most \(34 - 4 = 30\) doors, which means they have gone through at most 29 rooms in the maze. In this way, they can collect a maximum of 29 coins. However, if they have really gone through 29 rooms in the maze, they must have gone through all the doors except the 4 doors of the corner rooms. This means that on their path, they have also gone through the room with the entrance and exit, which does not have a coin. Therefore, they have visited a maximum of 28 rooms with coins and thus brought a maximum of 28 coins from the maze.

## 1. solution

Observation that a room with 3 doors can be entered only once, and a room with 4 doors up to twice ................................................ 1 point
Determination of the upper limit (30 coins) ................................................................................................................ 1 point
Finding that through one of the rooms with 4 doors adjacent to a corner room, the player can go only once ................................................ 2 points
Observation of opposite corner rooms and finding that the maximum number of coins decreases by at least 2 .................................................................................................................................................................

![](https://cdn.mathpix.com/cropped/2024_06_07_95af3fbbcea2fb458cf3g-15.jpg?height=52&width=1725&top_left_y=925&top_left_x=177)

Finding a possible path for 28 coins ................................................................................................................ 1 point

2. solution

Counting doors and finding that at least one door of each of the four rooms with 3 doors will not be used ................................................ 1 point

Optimal choice of doors (all 4 horizontal ones) through which the player does not go ................................................................................

Determination of the upper limit (\(34 - 4 = 30\) doors) ................................................................................................................

Determination of the upper limit (29 coins) ...................................................................................................... 1 point

Finding that when going through all 30 doors, the player also visits a room without a coin ................................................ 1 point

Correct answer of 28 coins ................................................................................................................ 1 point

![](https://cdn.mathpix.com/cropped/2024_06_07_95af3fbbcea2fb458cf3g-15.jpg?height=51&width=1727&top_left_y=1528&top_left_x=176)

Note. The points of the 1st and 2nd solutions are not additive.

67th Mathematical Competition for High School Students National Competition, April 22, 2023

# Solutions to tasks for 4th grade

![](https://cdn.mathpix.com/cropped/2024_06_07_95af3fbbcea2fb458cf3g-16.jpg?height=140&width=234&top_left_y=458&top_left_x=928)