## Saturday, March 17, 2007

### Frogger. Topic: Combinatorics. Level: AIME.

Problem: (2007 AIMEI - #6) A frog is placed at the origin on the number line, and moves according to the following rule: in a given move, the frog advances to either the closest point with a greater integer coordinate that is a multiple of $3$, or to the closest point with a greater integer coordinate that is a multiple of $13$. A move sequence is a sequence of coordinates which correspond to valid moves, beginning with $0$, and ending with $39$. For example, $0, 3, 6, 13, 15, 26, 39$ is a move sequence. How many move sequences are possible for the frog?

Solution: Let $S_k$ be the number of possible move sequences starting from $0$ and ending up at $k$. Clearly it is only interesting when $k$ is divisible by $3$ or $13$. So let's try to construct the sequence.

$S_0 = 1$ is our base case. There is only one way to get to the value $3$ from $0$, so $S_3 = 1$. Similarly, $S_6 = 1$, $S_9 = 1$, and $S_{12} = 1$. But how many ways can we get to $13$? Well, if we start at any of the previously mentioned numbers there we can go straight to $13$ from them (by using the next multiple of $13$ move). So

$S_{13} = S_0+S_3+S_6+S_9+S_{12} = 5$.

Now how about $S_{15}$? Well we can get there from either $12$ or $13$, so

$S_{15} = S_{12}+S_{13} = 6$.

Continuing, we have $S_{18} = S_{21} = S_{24} = 6$ because we can only get to these from the previous multiples of $3$. Then

$S_{26} = S_{13}+S_{15}+S_{18}+S_{21}+S_{24} = 29$.

In this similar fashion, we obtain $S_{27} = S_{30} = S_{33} = S_{36} = 35$ and finally $S_{39} = S_{26}+S_{27}+S_{30}+S_{33}+S_{36} = 169$. QED.

--------------------

Comment: This is a cool problem, though they could have made it harder to brute force (i.e. have the answer be $500+$) to really weed out the people who did not actually know how to intelligently count it. It is based on a nice recursive concept known as "dynamic programming," which is one of the coolest computer science techniques ever. The idea is to use solutions of subproblems to construct the solution to a larger problem, like in this case using smaller values of $S_k$ to calculate $S_{39}$.

--------------------

Practice Problem: (2007 AIMEI - #1) How many positive perfect squares less than $10^6$ are multiples of $24$?

1. Factorizing, $24=2^3\times 3$. For a number to be a perfect square, its prime factorization must have all even numbers. Therefore, the number must be $144=2^4\times 3^2$. There are 83 multiples of $144$ less than $10^6$.
You could still brute force up to $999$ :P