.
The following 7 × 22 grid is divided into squares that are 1 unit by 1 unit.
The shortest possible path on this grid from A to B is 29 units long.
One such path is shown in the figure. Let X be the set of all 29-unit-long paths from A to B.
Compute |X|, the number of 29-unit-long paths from A to B.
~~~~~~~~~~~~~~~~~~~~~~
Indeed, the figure is not shown, and it can perplex a reader.
But notice that 29 = 7 + 22, and it makes the meaning of the problem UNIQUE even without a plotted figure.
The points A and B are opposite vertices of the 7x22 rectangle
and the shown path is a path on the grid, comprised of vertical and horizontal segments
of the grid from corner A to corner B, such that a path represents
a piece-wide monotonic function.
For better understanding, this grid has 7 segments in one direction and 22 segments in other direction;
but the number of the vertices of the grid is (7+1) = 8 in one direction and (22+1) = 23 in the other direction.
We can think that 22 segments of the grid are horizontal and 7 segments are vertical,
and A is the left lowest corner of the grid, while B is the upper right corner.
So, we can think that the associated function is a piece-wide monotonically increasing.
The meaning of the problems remains the same at any other disposition of the grid
and the corners A and B.
Notice that vertical increments of the function are not necessary one vertical segment
of the grid: it can be two segments or three etc., but the governing rule is that the
associated function is a piece-wide MONOTONIC - it provides the shortest path.
Then it becomes CLEAR that this problem is the same as to ask,
in how many ways 22 (undistinguishable) objects can be distributed (placed) in 8
distinguishable boxes in a way that the empty boxes are allowed.
In other words, it can be re-formulated in this way: how many solutions this equation
+ + + + + + + = 22 (1)
may have in integer non-negative numbers , i = 1, 2, 3, . . . , 8.
In this form, it is a typical problem to be solved by the "stars-and-bars" method.
About this method, see this Wikipedia article
https://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29
or my lesson
- Stars and bars method for Combinatorics problems
in this site.
The answer is THIS: the number of solutions to equation (1) is
= = = 1560780.
ANSWER. The number of paths in this problem is 1560780.
Solved.