Hello. 👋
The rule is we are only allowed to use the the grid line (the border of each box) to reach the destination.
Shortest Path
Let's find the shortest path to reach the destination.
If we start from the top left, to go diagonally to the bottom right, we will have two options to move, those are: down — right. Other than those, we won't be going on the shortest path.
If we start from the bottom left, and we have to reach the top right, then we'll have two options, those are: up — right.
I put different colours, green and red, so you can see them. In that example, we have $6$ steps as our shortest path.
And therefore to actually get the shortest route is —
or —
Let's generalise the method.
For example $3$ by $3$ ($3$ rows, $3$ columns) grid above, the minimum steps from top left corner to bottom right corner will be:
The Arrangements
Now, right here, the brain teaser starts.
This is a problem in combinatorics.
Suppose those $6$ steps (shortest path we discovered) as the entire set. So the set consists of $6$ elements. Then we only have two options to move to get that shortest path. In the first example above, we will move $3$ downs and $3$ rights, or { D, D, D, R, R, R }. Or, in the second example, we will move $3$ ups and $3$ rights, or { U, U, U, R, R, R }.
Other than those moves, we cannot have shortest path. We need to jumble those elements and find how many different combinations can be arranged.
We can use the binomial coefficient — or "n choose k" (base combinatorial) formula to find the total number of possibilities.
This is the general formulation:
From the explanation above, thus we have:
n = 6
k = 3
Let's try that combinatorial formula, by substituting $n$ and $k$ with $n = 6$, $k = 3$ ⬇️
$_nC_k = (\table n; k) = n! / {k!·(n - k)!}$
$_6C_3 = (\table 6; 3) = 6! / {3!·(6 - 3)!}$
$= 6! / {3!·3!}$
$= {6·5·4·3·2·1} / {(3·2·1)·(3·2·1)}$
$= 120 / 6$
$= 20$
We have $20$ possible arrangements for $3 × 3$ grid ($3$ rows, $3$ columns) problem.
Sorted. ✅
The Swap — Symmetrical Property
If we have different problem, for instance, $3$ by $10$ ($3$ rows, $10$ columns) grid, then the size of shortest path will be $13$.
We can move $3$ verticals and $10$ horizontals.
Therefore, we have $n = 13$.
We may freely choose the $k$ to be $10$ OR $3$. Both will generate same result.
Using algebraic properties, we can prove that the combinatorial formula is symmetrical — meaning the result is the same whether we count choosing $3$ verticals out of $13$ steps, or choosing $10$ horizontals out of $13$ steps.
In other words, $(\table 13; 3)$ gives the same result as $(\table 13; 10)$.
$(\table n; k) = (\table n; {n-k})$
⬆️ It is because ${k!·(n - k)!}$ ➡️ while $n = k + other$ (total).
Multiset Permutation
This can also be seen as multiset permutation.
We can implement multiset permutation formula:
As $n$ represents total number of elements in the multiset.
$p$, $q$, $r$, and so forth, each one is how many times one specific item (criteria) appears.
Both combinatorial and multiset permutation formulations will yield similar result.
Animating the Arrangements
This is an example of animating that using jQuery features.
I put $3$ by $1$ grid setup. So we have $4$ steps for the shortest path, which consists of $3$ downs and $1$ right, or { D, D, D, R }.
Let's use multiset permutation to solve this.
We have $n = 4$, and the subsets $p = 3$ and $q = 1$.
$_4C_1 = (\table 4; 1) = 4! / {3!·1!}$
$= 4! / {3!·1!}$
$= {4·3·2·1} / {(3·2·1)·(1)}$
$= 4 / 1$
$= 4$
So we have $4$ possibilities to move with the shortest path for this $3 × 1$ grid ($3$ rows, $1$ column) setup.
Here is the demonstration to visualise it.
Demonstration 2013
|
A
|
|
B
|
Demonstration 2025
In this, we can set the start and end points dynamically.
Hover your cursor on the grid — then hover and click on any edge (corner) to set them, the total possibilities will be automatically calculated. And also, each route sequence can be animated.
The application below employs JavaScript, without jQuery library.
Independent Demonstration 2025
