3
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ A neat mathematical derivation, nice job! $\endgroup$ – Conifers Oct 3 '19 at 8:42
2
$\begingroup$

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);
| improve this answer | |
$\endgroup$

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.