Problem:
A frog is positioned at the origin in the coordinate plane. From the point (x,y), the frog can jump to any of the points (x+1,y),(x+2,y),(x,y+1), or (x,y+2). Find the number of distinct sequences of jumps in which the frog begins at (0,0) and ends at (4,4).
Solution:
Let r and R denote jumps right from (x,y) to (x+1,y) and (x+2,y), respectively, and let u and U denote jumps upward from (x,y) to (x,y+1) and (x,y+2), respectively. Then a jump sequence S from (0,0) to (4,4) must contain the jumps
1. exactly one of rrR (or any of its permutations), rrrr, or RR;
2. exactly one of uuU (or any of its permutations), uuuu, or UU.
Let N(S1​,S2​) denote the number of jump sequences whose respective subsequences of rightward and upward jumps are S1​ (or some permutation thereof) and S2​ (or some permutation thereof). The following table counts all the possible sequences of jumps.
(S1​,S2​)(rrrr, uuu)(RR, UU)(rrrr, UU)(RR, uuuu)​(rrrr, uuU)(rrR, uuuu)​(RR, uuU)(rrR, UU)​(rrR, uuU)​N(S1​,S2​)(48​)=70(24​)=6(26​)=15(4,2,17​)=105(2,2,15​)=30(2,2,1,16​)=180​​
The total number of jump sequences is obtained by adding the numbers in the second column that correspond to each row represented in the first column of the table. The requested number of jump sequences is therefore 70+6+2⋅15+ 2⋅105+2⋅30+180=556​.
OR
For integers a and b, let N(a,b) be the number of jump sequences that begin at (0,0) and end at (a,b). Then N(0,0)=1 and N(a,b)=0 if a<0 or b<0. For nonnegative integers a and b with a+b≥1, the given conditions imply the following recursion:
N(a,b)=N(a−1,b)+N(a,b−1)+N(a−2,b)+N(a,b−2)
Using this recursion to complete the following table shows that the requested number of jump sequences is 556​.
(0,0)​53211​2010521​71321452​2078432103​55620771205​(4,4)
The problems on this page are the property of the MAA's American Mathematics Competitions