There is an \(n\)-dimensional grid in an \(n\)-dimensional Euclidean space made of all points with integer coordinates of the form \((x_1, x_2, \dots, x_n)\) that satisfy the inequality \(0 \leq x_i \leq a_i\) where \(i \in \{1, 2, \dots, n\}\). Every pair of points in the grid that are a unit distance apart are connected by an edge. Through these edges, how many possible shortest paths are there from the point at \((0, 0, \dots, 0)\) to the point at \((a_1, a_2, \dots, a_n\))?

Sunday, July 15, 2012

Please email your solutions to puzzles@cotpi.com.

### 4 comments

### Credit

This is an original cotpi puzzle inspired by:

- "Problem 15." Project Euler 19 Apr. 2002. 20 July 2012 <http://projecteuler.net/problem=15>.

## Wonderwice Margera solved this puzzle:

Let \(A = \sum_{i=1}^n a_i\). Any path can be represented as a sequence of colors \(b_1, b_2, \dots, b_A\) where the colors are chosen from a set of \(n\) colors, \(\{c_1, c_2, \dots, c_n\}\), such that \(b_i = c_j\) if the \(i\)th step in the path was along the \(j\)th dimension. The correspondence between the set of paths and the set of such sequences is clearly a bijection.

Therefore, the given problem is identical to the problem of finding the number of ways of finding such a sequence, which is well known to be

\[\frac{A!}{\prod_{i=1}^n (a_i!)}.\]

## Tim Ophelders solved this puzzle:

Let us call the points in the grid nodes. Let the vector \( \newcommand{\v}{\mathbf{v}} \) \(\v = (v_0, v_1, \dots, v_n\)) represent a node at coordinates \((v_0, v_1, \dots, v_n)\). The shortest distance from the origin to \(\v\), in terms of edges is \( \newcommand{\x}{\mathbf{x}} \newcommand{\0}{\mathbf{0}} \)

\[d(\v) = \sum_{i=1}^n v_i.\]

The set of nodes adjacent to the node at \(\v\) in the shortest paths to \(\v\) is\[ p(\v) = \left\{ \x \mid d(\x) = \bigl(d(\v) - 1\bigr) \land \bigl(d(\v - \x) = 1\bigr) \right\}. \]

The component of \(\v\) that differs from a node \(\x \in p(\v)\) is

\[\Delta(\v, \x) = \v \cdot (\v - \x).\]

We prove by structural induction on paths that the number of shortest paths to \(\v\), is \(f(\v) = \frac{(d(\v))!}{\prod_{i=1}^n (v_i!)}\).

\begin{array}{cl|r} f(\0) & = \frac{(d(\0))!}{\prod_{i=1}^n (a_i!)} = \frac{0!}{(0!)^n} = 1 & \text{ i.e. only the empty path} \\ f(\v) & = \sum_{\x \in p(\v)} f(\x) & \\ & = \sum_{\x \in p(\v)} \frac{(d(\x))!}{\prod_{i=1}^n (x_i!)} & \\ & = \sum_{\x \in p(\v)} \frac{(d(\v) - 1)!}{\prod_{i=1}^n (x_i!)} & d(x) = d(v) - 1 \\ & = \sum_{\x \in p(\v)} \frac{(d(\v) - 1)!}{\prod_{i=1}^n (v_i!)} \cdot \Delta(\v, \x) & \prod_{i=1}^n (v_i!) = \Delta(\v, \x) \prod_{i=1}^n (x_i!) \\ & = \frac{(d(\v) - 1)!}{\prod_{i=1}^n (v_i!)} \sum_{\x \in p(\v)} \Delta(\v, \x) & \\ & = \frac{(d(\v) - 1)!}{\prod_{i=1}^n (v_i!)} \sum_{i=1}^n v_i & \sum_{\x \in p(\v)} \Delta(\v, \x) = \sum_{i=1}^n v_i \\ & = \frac{(d(\v))(d(\v) - 1)!}{\prod_{i=1}^n (v_i!)} & \\ & = \frac{(d(\v))!}{\prod_{i=1}^n (v_i!)} & \\ \end{array}

Therefore, the number of shortest paths from the origin to \((a_1, a_2, \dots, a_n)\) is

\[ \frac{\left(\sum_{i=1}^n a_i\right)!} {\prod_{i=1}^n (a_i!)}. \]

## Rino Raj solved this puzzle:

Let \(m = \sum_{i=1}^n a_i\). Then all shortest paths have length \(m\), and each step can be denoted by just \(i\), the direction or dimension in which the step is taken. Thus each shortest path can be encoded by a string of \(m\) digits, where each digit \(i \in \{1, 2, \dots, n\}\) occurs exactly \(a_i\) times. Every such string represents a valid shortest path, so the number of such strings is the same as the number of shortest paths.

The number of such strings is counted by the multinomial coefficient

\[\frac{m!}{\prod_{i=1}^n (a_i!)}.\]

## Eric Sosman solved this puzzle:

Assuming there are no bridges other than the unit steps mentioned in the puzzle, each step in any path changes one coordinate by one unit. A shortest path thus needs \(\sum_{i=1}^n a_i\) steps in all, \(a_k\) along the \(k\)th axis. Therefore, the number of shortest paths is the number of permutations of \(a_1\) steps along the first axis, \(a_2\) steps along the second axis, and so on, which is given by the expression

\[\frac{\left(\sum_{i=1}^n a_i\right)!}{\prod_{i=1}^n (a_i!)}.\]