4
$\begingroup$

Imagine you have a big rectangular pond in your back garden. You wish to build a bridge from your house in the lower left corner to the small pagoda in the top right.

You have lots of planks of length $1$ and $2$. You only wish to place planks orthogonal to the sides of the pond, and you don't want to go backwards ever. The pond is $10\times10$.

How many ways are there to do this?

For example:

. . . ._P
      |
. . . . .
      |
. . . . .
      |
. . ._. .
    |
H_._. . .

For a bonus, is there a generic solution for planks of length $l_1,l_2,\dots,l_k$?

$\endgroup$
8
$\begingroup$

Rather than thinking of planks as having lengths, think of them as defining certain sets of vectors. So in this case we have (1,0), (0,1), (2,0), (0,2). (Caution: if you have e.g. a plank of length 5 then you need to allow (3,4) and (4,3) as well as (5,0) and (0,5)! [EDITED to add:] No, as pointed out by another user in comments that's wrong because the question specifies orthogonal only. Though obviously you could also do it the other way if you wanted :-).)

Now we have a recurrence relation: if we write $N(a,b)$ for the number of ways to span a pond of size $(a,b)$ then we have $N(0,0)=1$ and $N(a,b)=\sum N(a-x,b-y)$ where the sum is over plank-vectors $(x,y)$.

For the particular case here, the table looks like this:

$$\begin{array}{r} 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 \\ 1 & 2 & 5 & 10 & 20 & 38 & 71 & 130 & 235 & 420 & 744 \\ 2 & 5 & 14 & 32 & 71 & 149 & 304 & 604 & 1177 & 2256 & 4266 \\ 3 & 10 & 32 & 84 & 207 & 478 & 1060 & 2272 & 4744 & 9692 & 19446 \\ 5 & 20 & 71 & 207 & 556 & 1390 & 3310 & 7576 & 16807 & 36331 & 76850 \\ 8 & 38 & 149 & 478 & 1390 & 3736 & 9496 & 23080 & 54127 & 123230 & 273653 \\ 13 & 71 & 304 & 1060 & 3310 & 9496 & 25612 & 65764 & 162310 & 387635 & 900448 \\ 21 & 130 & 604 & 2272 & 7576 & 23080 & 65764 & 177688 & 459889 & 1148442 & 2782432 \\ 34 & 235 & 1177 & 4744 & 16807 & 54127 & 162310 & 459889 & 1244398 & 3240364 & 8167642 \\ 55 & 420 & 2256 & 9692 & 36331 & 123230 & 387635 & 1148442 & 3240364 & 8777612 & 22968050 \\ 89 & 744 & 4266 & 19446 & 76850 & 273653 & 900448 & 2782432 & 8167642 & 22968050 & 62271384 \end{array} $$

The number you want is in the bottom right of the array. This happens to be http://oeis.org/A036355. In general, the generating function for these things is $\frac1{1-\sum x^{dx}y^{dy}}$ where the sum is over plank-vectors $(dx,dy)$. I guess you can probably get a closed form out of that somehow.

$\endgroup$
  • 2
    $\begingroup$ I was about to post the same table. :-) $\endgroup$ – Jaap Scherphuis Mar 22 at 13:42
  • 1
    $\begingroup$ Why am I not surprised that the person saying that is you? :-) $\endgroup$ – Gareth McCaughan Mar 22 at 13:49
  • 9
    $\begingroup$ On my computer, the table spills over into the HNQ. Maybe just me? $\endgroup$ – Brandon_J Mar 22 at 14:13
  • 1
    $\begingroup$ @GarethMcCaughan The (3,4)/(4,3) bit is wrong, and confused me for a minute before I realized what you meant. You can't place planks on an angle like that, since the question specified that planks must be "orthogonal to the sides of the pond". $\endgroup$ – Billy Mailman Mar 22 at 16:28
  • 1
    $\begingroup$ @Brandon_J Not just you, me too $\endgroup$ – Sensoray Mar 22 at 19:17
2
$\begingroup$

My answer (using a computer program) is:

There are 8777612 ways to arrange the planks.
I solved this using a C program

#include <stdio.h>

#define WIDTH 10
#define DEPTH 10
#define PLANK 2

unsigned long long cache[DEPTH][WIDTH];

unsigned long long recur(int row, int col) {
if(row >= DEPTH || col >= WIDTH)
return 0;
if(row == DEPTH-1 && col == WIDTH-1)
return 1;
if(cache[row][col] != 0)
return cache[row][col];

unsigned long long paths = 0;
for(int p = 1; p <= PLANK; p++) {
paths += recur(row + p, col);
paths += recur(row, col + p);
}
cache[row][col] = paths;
return paths;
}

int main(void) {
printf("Paths = %llu\n", recur(0, 0));
}

Note that this is from coordinate (0,0) to (9,9) because the start and finish points are in the pond. The distance is $9$ in each direction. It checks out when manually counting small ponds.

This also provides a generic solution for ponds up to $26 \times 26$, or up to $2^{64}-1$ paths.
For small ponds the cache isn't necessary.

$\endgroup$
  • $\begingroup$ @JonMarkPerry isn't the other answer for 11 x 11 pond? Count across the table. $\endgroup$ – Weather Vane Mar 22 at 14:49

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.