Path on a chessboard

109 Views Asked by At

Consider a chess board and a pawn. The game is simple (and I'm sure you have all heard it before), pawn wants to move from position (1,1), or the bottom left corner, all the way to (n,n), or the upper right corner. We are asked to find all possible paths this pawn could take.

This problem is not all that hard, considering that the path always takes $2n-2$ moves. Cancelling out the same, but reversed and tidying up the formula, we get

$$\binom{2n-2}{n-1}$$ possible paths.

Following which, the main question is what would happen if we removed some pivotal squares. Let's consider that we have a chessboard with $n=4$, and were to remove square $(3,3)$. By my logic, all we need to do is to find all the possible ways how to get to $(4,4)$ and to $(3,3)$. Then we would subtract all the ways to $(3,3)$ from the number of paths to $(4,4)$, which would give us

$$\binom{2*4-2}{4-1} - \binom{2*3-2}{3-1} =$$ $$\binom{6}{3} - \binom{4}{2} =$$ $$20 - 6 = 12$$

As I found out, this is not the correct solution. I mapped out all the possible paths, and found only $8$ of them. If we multiply the number of paths to $(3,3)$ by $2$, that would give us the correct solution; $$\binom{2*4-2}{4-1} - 2* \binom{2*3-2}{3-1} =$$ $$20 - 2*6 = 8$$

That begs the question, is the second solution correct? And if so, why? That, I do not know.

Additionally, what would happen if we were to remove more than one square? For example, let $n=13$ and lets remove two squares, $(5,5)$ and $(8,8)$. Would that be something like

$$\binom{2*13-2}{13-1} - 2* {\left[\binom{2*8-2}{8-1} + \binom{2*5-2}{5-1}\right]}$$

or did I get the whole concept wrong? Why is there that seemingly random multiplication, and how would it stack with more and more pivotal squares removed?

1

There are 1 best solutions below

2
On

The paths to $(4,4)$ that use $(3,3)$ aren't just paths to $(3,3)$; their paths to $(3,3)$ and then on to $(4,4)$. So to count them, you need to multiply the number of ways to get from $(1,1)$ to $(3,3)$, which you calculated, with the number of ways to get from $(3,3)$ to $(4,4)$. That's $\binom21=2$, and this is where the missing factor $2$ comes from.

If you remove more than one square, you need to use inclusion–exclusion. For each subset of the removed squares, you need to add or subtract the number of paths that use that subset of removed squares, according as it contains an even or odd number of removed squares. (That number will be zero unless the orders of the $x$ and $y$ coordinates of the squares coincide.)

For instance, if you remove the squares $(2,2)$ and $(3,3)$, you're left with $4$ paths, and this can be calculated as follows, with $N(S)$ denoting the number of paths that use all squares in $S$:

\begin{eqnarray*} &&N(\emptyset)-N(\{(2,2)\})-N(\{(3,3)\})+N(\{(2,2),(3,3)\})\\ &=& \binom63-\binom21\binom42-\binom42\binom21+\binom21\binom21\binom21\\ &=& 20-2\cdot6-2\cdot6+2\cdot2\cdot2\\ &=& 20-12-12+8\\ &=& 4\;. \end{eqnarray*}