That Creepy Extra Area Under the Stairs

Probability Level 2

Start in the lower left corner of a 5x10 unit grid. You may only move to the right and upward along the edges to get to the top right corner. The area of a path between the corners is the amount of area beneath the line in square units. For example:

On a 5x10 grid, how many different paths from the lower left corner to the upper right corner have an area congruent to 1 mod 5?

Bonus: Choose any prime $p$ and positive integers $i<p$ , $j$ and $k$ and generalize this solution to the number of paths with an area congruent to $i$ mod $p$ on a $jp$ by $kp$ grid.

100

800

300

600

500

1 solution

Zandra Vinegar Staff
Oct 18, 2015

(Generalized formula and proof by Bill Kuszmaul)

Let $j$ and $k$ be positive integers and let $p$ be prime. Consider a path $w$ containing $jp$ vertical steps and $kp$ side steps. Suppose there exists a $r$ such that the steps $w_{pr+1}, \dots, w_{p(r+1)}$ are not all either just ups or just rights. Let $r$ be the smallest such $r$ . Then, we can "cancel out" the area of $w$ with the area of the paths reached by taking $w$ and cyclicly shifting the steps $w_{pr+1}, \dots, w_{p(r+1)}$ within $w$ . The paths we have "cancelled out" with each other have areas equidistributed modulo $p$ . Now let us consider the remaining paths. Each such path consists of chunks of $p$ side steps and $p$ vertical steps appended together. Each such path, as a consequence, has area $0$ mod $p$ , and there are exactly $j+k \choose j$ such paths. Hence, the number of paths on a $jp \times kp$ grid with area $0$ mod $p$ is:

$\frac{{jp+kp \choose jp}-{j+k \choose j}}{p}+{j+k \choose j}$

And the number of paths with area $i$ mod $p$ for $i$ not congruent to zero is

$\frac{{jp+kp \choose jp}-{j+k \choose j}}{p}$

=================

Therefore, for $p = 5; j=1; k=2$ , the answer is $\frac{{1(5)+2(5) \choose 1(5)}-{1+2 \choose 1}}{5} = \frac{{15 \choose 5}-{3 \choose 1}}{5} = \frac{{3003}-{3}}{5} = 600$

Nice. At first I wondered whether you needed to give a proof for this statement: "The paths we have "cancelled out" with each other have areas equidistributed modulo p." But now I see it's pretty simple: with each cyclical-shift the area changes by the same amount, mod p.

Peter Byers - 5 years, 1 month ago

can you explain what you mean by cyclicity shifting the steps? also, i don't quite know what the subscript of w is suppose to mean because when you defined w, there was no subscript there. thanks!!!

Willia Chang - 5 years ago

That Creepy Extra Area Under the Stairs

1 solution

0 pending reports