# 6. Variant 1.

In the district, there are three villages $A, B$, and $C$ connected by dirt roads, with any two villages being connected by several (more than one) roads. Traffic on the roads is two-way. We will call a path from one village to another either a road connecting them or a chain of two roads passing through a third village. It is known that villages $A$ and $B$ are connected by 34 paths, and villages $B$ and $C$ by 29 paths. What is the maximum number of paths that can connect villages $A$ and $C$?
Answer: 106.

Solution.

Let there be $k$ roads between cities $A$ and $B$, $m$ roads between cities $B$ and $C$, and $n$ roads between cities $A$ and $C$. Then the number of paths from $A$ to $B$ is $k + mn$, and the number of paths from $B$ to $C$ is $m + kn$. We have the system of equations $k + mn = 34$, $m + kn = 29$, where the unknowns are natural numbers greater than 1. Subtracting the second equation from the first, we get: $(m - k)(n - 1) = 5$. We need to check all divisors of 5: 1 and 5. Therefore, $n = 2$ or $n = 6$. For each of them, we find $m$ and $k$ by solving the corresponding system of linear equations. If $n = 2$, then $k = 8$ and $m = 13$. If $n = 6$, then $k = 4$ and $m = 5$. The number of paths connecting cities $A$ and $B$ is $n + km$. In the first case, $n + km = 2 + 8 \cdot 13 = 106$, and in the second case, $-n + km = 6 + 4 \cdot 5 = 26$. Therefore, the desired answer is 106.