5. A rectangle $3 \times 5$ is divided into 15 squares $1 \times 1$. We will call a path a movement along the sides of the unit squares, such that no side is traversed more than once. What is the maximum length that a path connecting two opposite vertices of the rectangle can have?
Answer: 30.

Solution. Let the rectangle be denoted as $A B C D$, and let the path connect its vertices $A$ and $C$. We will call the sides of the $1 \times 1$ squares edges, the vertices of these squares - nodes, and the number of edges adjacent to a node - the multiplicity of the node. Note that the $1 \times 1$ squares generate 38 different edges. If the path passes through a node of multiplicity 3, then it enters the node along one edge and exits along another, while the third edge adjacent to the node cannot belong to the path. Let $X$ be the set of nodes lying on the broken line $B A D$, excluding points $B$ and $D$. It consists of point $A$ and six nodes of multiplicity 3. Note that point $A$ has multiplicity 2, and the path does not enter it. Therefore, for each node in $X$, there is an edge free from the path (regardless of whether the path passes through the given node or not). For non-adjacent nodes, these edges are certainly different, and there cannot be more than 3 pairs of adjacent nodes. Thus, the set $X$ provides at least 4 edges free from the path. The same reasoning applies to the broken line $B C D$. Therefore, there are at least $2 \cdot 4 = 8$ edges free from the path, and the length of the path does not exceed $38 - 8 = 30$. An example of a path of length 30 is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_06_bd69057b1c245517edf6g-14.jpg?height=382&width=576&top_left_y=1668&top_left_x=817)