0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ But you know... pawns can only move forward... and occasionally attack diagnally... until they become something else. $\endgroup$
    – WhatsUp
    Dec 2, 2019 at 21:58

1 Answer 1

1
$\begingroup$

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*}

$\endgroup$
2
  • $\begingroup$ So for the last case that would be $\binom{24}{12}-\binom84\binom{14}{7}-\binom{14}{7}\binom84+\binom84\binom84\binom84\\$, right? $\endgroup$
    – igor
    Dec 3, 2019 at 11:20
  • $\begingroup$ @Igor: Almost; I think some of your counts are off by $1$. The lower index is always the coordinate difference between the squares you're connecting. So if you're going from coordinate $1$ to $13$ while avoiding $5$ and $8$, that would be $$ \binom{24}{12}-\binom84\binom{16}8-\binom{14}7\binom{10}5+\binom84\binom63\binom{10}5\;. $$ As a check, the indices (both upper and lower) in the factors of each term should add up to the same sum. $\endgroup$
    – joriki
    Dec 3, 2019 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.