5. A square $4 \times 4$ is divided into 16 squares $1 \times 1$. We will call a path a movement along the sides of the unit squares, in which no side is traversed more than once. What is the maximum length that a path connecting two opposite vertices of the large square can have?
Answer: 32.

Solution. Let's 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. Notice that the $1 \times 1$ squares generate 40 distinct edges. If a path passes through a node of multiplicity 3, it enters the node along one edge and exits along another, while the third edge adjacent to the node cannot belong to the path. Consider a triplet of nodes of multiplicity 3 lying on one side of the $4 \times 4$ square. Each node has an edge adjacent to it that is free from the path (regardless of whether the path passes through the node or not), and for non-adjacent nodes, these edges are different. Therefore, there are at least $2 \cdot 4 = 8$ edges free from the path, and the length of the path does not exceed $40 - 8 = 32$. An example of a path of length 32 is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_06_bd69057b1c245517edf6g-10.jpg?height=446&width=454&top_left_y=942&top_left_x=867)