XXXVIII OM - III - Problem 6

A plane is covered with a grid of regular hexagons with a side length of 1. A path on the grid is defined as a sequence of sides of the hexagons in the grid, such that any two consecutive sides have a common endpoint. A path on the grid is called the shortest if its endpoints cannot be connected by a shorter path. Find the number of shortest paths on the grid with a fixed starting point and a length of 60.
Attention. The phrase "consecutive sides have a common end" used in the text should be understood to mean that directed segments are considered, and the end of the previous one is the start of the next (thus, it does not form a path, for example, a star of segments with one common end). Despite the lack of precision, this formulation was understood by all solvers in this way, in accordance with the intuitive sense of the word "path."
Let us establish one of the directions of the sides of the considered hexagonal grid ($ \Sigma_6 $), let's call it horizontal and distinguish the directions on it: left, right. From each node of the grid $ \Sigma_6 $, exactly one horizontal side extends. Let $ W $ denote the set of nodes from which the horizontal side extends to the right, and $ W $ the set of the remaining nodes, that is, those from which the horizontal side runs to the left. Each side of the grid connects a point of the set $ W $ with a point of the set $ W $.
Let $ O $ be a selected fixed node, the starting point of the considered paths. We can assume that $ O \in W $. Starting from point $ O $, after an even number of steps, we will find ourselves at a point of the set $ W $, and after an odd number - at a point of the set $ W $. Therefore, two paths with a common start and end have the same parity of length; if a path can be shortened - then by at least $ 2 $.
Two different points of the set $ W $ will be called adjacent if they are connected by a path of length $ 2 $; this path is then unique. Let us connect each pair of adjacent points of the set $ W $ with a segment. In this way, a grid $ \Sigma_3 $ of equilateral triangles with side $ \sqrt{3} $ will arise; the nodes of the grid $ \Sigma_3 $ are the points of the set $ W $. We define the concept of a path on the grid $ \Sigma_3 $, the length of the path, and the concept of the shortest path analogously to the corresponding concepts for the grid $ \Sigma_6 $, with the exception that we take the side of the grid $ \Sigma_3 $ as the unit of length.
In the following, we will consider only paths of even length on the grid $ \Sigma_6 $, starting at point $ O $ and satisfying the following condition: if $ OP_1P_2 \ldots P_{2k-1}P_{2k} $ is the considered path, then $ P_{2i-2} \neq P_{2i} $ for $ i = 1, \ldots, k $ (we assume $ P_0 = O $); in other words, no side of the grid is traversed "there and back" in two consecutive steps, the first of which has an odd number and the second an even number (of course, every shortest path satisfies this condition). By following such a path, in each subsequent pair of steps, one moves from a point of the set $ W $ to an adjacent point of the set $ W $. Therefore, each path on the grid $ \Sigma_6 $ that satisfies this condition and has length $ 2k $ determines a path of length $ k $ on the grid $ \Sigma_3 $. This is a one-to-one correspondence, because the ends of each side of the grid $ \Sigma_3 $ are connected by exactly one path of length $ 2 $ on the grid $ \Sigma_6 $. Shortest paths on one grid correspond to shortest paths on the other grid.
We will try to count the shortest paths of length $ k $ on the grid $ \Sigma_3 $ (starting at $ O $).
Consider six paths (on the grid $ \Sigma_3 $) of length $ k $ starting from $ O $ and running along rays. Their ends are the vertices of a regular hexagon, which we will denote by $ H_k $. By starting from point $ O $ and making $ k $ moves (on the grid $ \Sigma_3 $), we will not leave the strip bounded by the lines containing any two parallel sides of the hexagon $ H_k $ - and thus we will not leave the area of this hexagon. We can, however, reach any point lying on its boundary. Moreover, any node of the grid $ \Sigma_3 $ lying inside $ H_k $ belongs to some hexagon $ H_j $, where $ j < k $, and therefore is reachable by a path of length $ j $. Therefore, only the points on the boundary of $ H_k $ are reached by the shortest paths of length $ k $ (on the grid $ \Sigma_3 $).
How many such paths are there? Any side $ AB $ of the hexagon $ H_k $ contains $ k+1 $ points of the set $ W $, and if we number them $ Q_0, \ldots, Q_k $ ($ Q_0 = A $, $ Q_k = B $), we will notice that $ \binom{k}{r} $ shortest paths lead from point $ O $ to point $ Q_r $; this follows by easy induction from the observation that the shortest paths to any of the points $ Q_0, \ldots, Q_{k-1} $ are extensions of the shortest paths to two adjacent nodes on the boundary of the hexagon $ H_{k-1} $, and to points $ A $ and $ B $ there is one path of length $ k $ each. (In other words: by writing in each node of the grid $ \Sigma_3 $ the number of shortest paths from point $ O $ to the given node, we obtain six copies of Pascal's triangle, one in each of the six sectors of the plane with vertex $ O $, determined by the directions of the sides of the grid $ \Sigma_3 $). There are thus $ 2^k $ shortest paths connecting $ O $ with the points of side $ AB $.
The hexagon $ H_k $ has six sides. We therefore have $ 6 \cdot 2^k - 6 $ shortest paths to points on the boundary of $ H_k $; the term $ -6 $ prevents the double counting of paths leading to the vertices of $ H_k $.
The task is to determine the number of shortest paths (starting at $ O $) of length $ 60 $ on the grid $ \Sigma_6 $, i.e., the number of shortest paths (starting at $ O $) of length $ 30 $ on the grid $ \Sigma_3 $. According to the above considerations, this number is $ 6 \cdot 2^{30} - 6 $.