## Task 4 - 220614

The image a) shows a part of a city map. A car is to drive from $A$ to another intersection, e.g., $X$, on the shortest possible route. As an example, one such route is marked. We want to know for each intersection $Z$ different from $A$ - how many different shortest routes from $A$ to $Z$ there are in total.

![](https://cdn.mathpix.com/cropped/2024_06_06_b85a894aa8dbf722a7b3g-0237.jpg?height=460&width=763&top_left_y=1432&top_left_x=652)

a) First, find all the intersections to which there is exactly one shortest route from $A$!

b) The image b) represents a section from image a), where $Z$ is one of the intersections not considered in a). If we already know how many shortest routes there are from $A$ to $U$ and how many shortest routes there are from $A$ to $V$, how can we then calculate the total number of shortest routes from $A$ to $Z$?

c) Use the considerations from a) and b) to find the desired number for each of the eleven intersections $Z$ different from $A$!

d) Determine the number of shortest routes from $A$ to $X$ in image a) again in a different way:

Write each of these routes by specifying the directions of its five segments! Use abbreviations, e.g., h for horizontal, v for vertical!
a) In the figure, the sought intersections are marked with 1.

b) Every possible shortest path from $A$ to $Z$ leads either through $U$ or through $V$. From $U$ or $V$, however, there is only one way to get to $Z$ in the shortest possible manner.

Thus, the total number of shortest paths from $A$ to $Z$ can be calculated by adding the corresponding numbers for $U$ and $V$.

c) Starting from the intersections found in a), the numbers are found successively using the reasoning from b):

$$
2=1+1, \quad 3=1+2, \quad 4=1+3, \quad 6=3+3, \quad 10=4+6
$$

in the figure.

d) There are exactly the following shortest paths from $A$ to $X$:

$$
\begin{aligned}
& \text { S S S W W, } \\
& \text { S S W S W, } \\
& \mathrm{S} \mathrm{S} \mathrm{W} \mathrm{W} \mathrm{S,} \\
& \text { S W S S W, } \\
& \mathrm{S} \mathrm{W} \mathrm{S} \mathrm{WS} \\
& \mathrm{S} \mathrm{W} \mathrm{W} \mathrm{S} \mathrm{S,} \\
& \text { W S S S W, } \\
& \text { W S S W S, } \\
& \text { W S W S S, } \\
& \text { W W S S S. }
\end{aligned}
$$

Their enumeration was done here "lexicographically" (i.e., according to the rule for ordering in a dictionary), which provides a better overview to ensure completeness.

Solutions of the I. Round 1982 adopted from $[5]$

### 3.23.2 II. Round 1982, Class 6