# Cross the pond, but there's a catch!

There is a square pond, conveniently divided into segments, with coordinate $$(0,0)$$ in the bottom left and $$(10,10)$$ is the top right.

You have planks length $$2$$ and $$3$$. You start at $$(0,0)$$ and must get to $$(10,10)$$. Each plank is to be laid either horizontally or vertically, and bottom-left to top-right (no going backwards).

A similar question, with an answer as to how to approach this problem, is here.

The catch is that this pond has a very dangerous whirlpool at coordinates $$(5,5)$$, and this square cannot be landed on, but it can be passed over.

How many ways can we build a bridge across this pond?

So, there is actually an approach by hand (without calculating via a computer program or creating a $$10 \times 10$$ table of a recurrence relation).

Observe that to get a distance of $$10$$ by using planks of length $$2$$ and $$3$$:

We are using exactly $$4$$ planks, except a case of using $$5$$ $$2$$'s. If we are using $$4$$ planks, we will use exactly $$2$$ $$2$$'s and $$2$$ $$3$$'s, making $$\binom{2+2}{2}=6$$ combination cases.

Thus, from $$(0,0)$$ to $$(10,10)$$, the number of ways — including going into the whirlpool — is:

- Using $$5$$ planks on horizontal and $$5$$ planks on vertical: $$\binom{5+5}{5} = 252$$.
- Using $$5$$ planks on horizontal and $$4$$ planks on vertical: $$\binom{5+4}{5} \times 6 = 756$$.
- Using $$4$$ planks on horizontal and $$5$$ planks on vertical: $$\binom{5+4}{4} \times 6 = 756$$.
- Using $$4$$ planks on horizontal and $$4$$ planks on vertical: $$\binom{4+4}{4} \times 6 \times 6 = 2520$$.

Overall, there will be $$252+756+756+2520=4284$$ ways.

Now, we may then count how many ways of going from $$(0,0)$$ to $$(10,10)$$ and landing on $$(5,5)$$. It's simply:

Count the number of ways going from $$(0,0)$$ to $$(5,5)$$, multiplying the number of ways going from $$(5,5)$$ to $$(10,10)$$.

Again, using a similar observation to get a distance of $$5$$ and going from $$(0,0)$$ to $$(5,5)$$ (and also $$(5,5)$$ to $$(10,10)$$):

We are using exactly $$2$$ planks: $$1$$ $$2$$'s and $$1$$ $$3$$'s, making $$2$$ possible cases.
Using $$2$$ planks on horizontal and $$2$$ planks on vertical: $$\binom{2+2}{2} \times 2 \times 2 = 24$$ ways.

So, the final answer will be:

$$4284 - (24 \times 24) = 3708$$ ways.

• A neat mathematical derivation, nice job! Oct 3 '19 at 8:42

Using the following program I get

3708

let result = 0;
go(0, 0);
function go(x, y) {
if(x === 10 && y === 10) {
result++;
return;
}
if(x > 10 || y > 10 || (x === 5 && y === 5)) {
return;
}
go(x + 2, y);
go(x + 3, y);
go(x, y + 2);
go(x, y + 3);
}
console.log(result);