$\mathrm{Na}$ in the zoo, they opened a maze for the children with six stations where candies were being distributed. At one station, 5 candies were given out with each entry, at two stations, 3 candies were given out, and at three stations, 1 candy was given out. Jirka first entered the station marked with an arrow and continued in such a way that he walked each path no more than once.

Determine the maximum number of candies Jirka could get.

(E. Novotná)

![](https://cdn.mathpix.com/cropped/2024_04_17_f09179dc58e2e20ca09dg-1.jpg?height=489&width=445&top_left_y=1880&top_left_x=1408)
The most candies Jirka can get is when he walks each path exactly once, and the stations he visits most frequently distribute the most candies. It is possible to walk the maze in the specified way, for example, the path

$$
\mathrm{A}-\mathrm{B}-\mathrm{C}-\mathrm{D}-\mathrm{E}-\mathrm{C}-\mathrm{A}-\mathrm{E}-\mathrm{F}-\mathrm{A}
$$

according to the labeling as shown in the image.

![](https://cdn.mathpix.com/cropped/2024_04_17_f09179dc58e2e20ca09dg-2.jpg?height=482&width=460&top_left_y=290&top_left_x=798)

There are also other possible paths, but it is not necessary to analyze them. What is essential is that we can determine how many times each station can be entered. This does not depend on the chosen path but only on the number of paths leading to a given station. Two paths lead to stations $B, F$, and $D$, while four paths lead to stations $\mathrm{A}, \mathrm{C}$, and $\mathrm{E}$. Moreover, station A can be entered from outside, while the other stations can only be passed through (i.e., the number of entries equals the number of exits). Therefore,

- Jirka can enter station A three times (once from outside, once while passing through, and finally ending there),
- Jirka can enter each of the stations $\mathrm{C}$ and $\mathrm{E}$ twice (i.e., twice while passing through),
- Jirka can enter each of the stations $\mathrm{B}, \mathrm{D}$, and $\mathrm{F}$ only once (i.e., once while passing through).

Thus, Jirka could get the most candies if 5 candies were distributed at station A, 3 candies at stations $\mathrm{C}$ and $\mathrm{E}$, and 1 candy at the remaining stations. In this case, Jirka would get 5 candies three times at one station, 3 candies twice at two stations, and 1 candy at three stations, i.e.,

$$
3 \cdot 5 + 2 \cdot 3 + 2 \cdot 3 + 3 \cdot 1 = 30
$$

candies.

Scoring suggestion. 2 points for determining a path that walks each path exactly once; 2 points for calculating the visit frequency of each station; 1 point for assigning the number of candies distributed at each station; 1 point for the correct total candy gain.