This is a brain teaser.
The rule is we are only allowed to use the the grid line (the border of each box) to reach the destination.
Finding the Shortest Path
Let's right away find the shortest path to reach the destination.
We need to pick only two directions from all four directions: up-down-right-left. And the two must be perpendicular to each other.
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 colors, green and red, so you can see them. In that example, we have 6 steps as our shortest path.
How to Actually Get the Shortest Route (Steps)?
By counting along the side borders of the grid.
Or
Adding the total rows and columns.
Let's generalize 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:
${Total Rows} + {Total Columns}$
3 + 3
6
The Arrangements
How many ways the shortest path arrangements can we build from that example above?
Now, right here, the brain teaser starts.
This is a problem in combinatorics.
Suppose those 6 steps (the shortest path we discovered) as the entire space (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 the shortest path. We need to scramble 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:
$_nC_k = (\table n; k) = n! / {k!·(n - k)!}$
From the explanation above, thus we have:
n = 6
k = 3
For simplicity, let's use that combinatorial formula, by substituting those 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$
And the answer is 20.
We have 20 possible arrangements for 3 × 3 grid (3 rows, 3 columns) problem.
Switcheroo
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 the 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 of this switcheroo-a-magic-jar-in-your-face part ➡️ ${k!·(n - k)!}$ ➡️ While $n = k + other$ (total) 💡
Side note starts.
This can also be seen as multiset permutation.
We can also implement the multiset permutation formula:
$n! / {p!·q!·r!·...}$
As n represents the 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.
Side note ends.
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.
I guess my explanation above was going all over the place, hence to make it more visual, here is the demonstration.
Click and watch the demo below.
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 does not use jQuery.
Independent Demonstration 2025
✅ Feel free to use this demonstration anywhere for visualization — the code is free to use.
Comments
Post a Comment