This is the chessboard, where A and B are the 2 ends of the board. An ant starts from end A, and can only move forwards (horizontally) and upwards (vertically). The ant cannot move diagonally and is not allowed to move backwards or be on a tile on more than one occasion. What is the number of ways in which the ant can reach the end B, from end A, on the chessboard?
My attempt:
I viewed each crossing as a $^2C_1$ scenario (to go either upward or forwards). We know that once the ant reaches the edge of the board, it can only go upward ie. only 1 option for movement is available. So I made cases for each leftmost horizontal tile the ant is on.
For crossing 8 tiles horizontally we have ${(^2C_1)}^{8}$.
In the first case, we go up by ${(^2C_1)}^{0})$. (0 tiles are travelled vertically along the 8 horizontal tiles).
In the second case, we go up by ${(^2C_1)}^{1}$ (1 tile is travelled vertically, somewhere along those 8 horizontal tiles).
In the third case, we go up by ${(^2C_1)}^{2}$ (2 tiles are travelled vertically, somewhere along those 8 horizontal tiles).
and so on. This sequence occurs 7 times as the ant is already on the 1st horizontal row of tiles.
Hence, the total sum is:
$$2^{8} + 2^{8}*2+ 2^{8}*2^{2}+ 2^{8}*2^{3}+ 2^{8}*2^{4}….+ 2^{8}*2^{7}$$
$$2^{8}(1 + 2^{1} + 2^{2} + …. 2^{7})$$
$$2^{8}(2^{7}-1)$$
$$256 \times 127$$
$$32512$$
We then multiply this number by 2, to account for those cases where the ant makes it journey till the uppermost and leftmost point of the board before proceeding forward to B.
Giving us,
$65024$
But it seems this answer is incorrect.
So how do you solve this intriguing Chessboard Permutation problem?
Best Answer
A correct path that joins $A$ to $B$ is made of $14$ steps, with $7$ steps up and $7$ steps right.
So basically, the question is : how many such paths are there ?
The answer is : in the $14$ steps, you just have to choose the $7$ ones where you go up ; the steps where you go right will be deduced immediately.
So there are $C_{14}^7$ such paths, which gives $$3432 \text{ possibilities}$$