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 $?
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$.
ReplyDeleteYou mean there are 83 square multiples of 144 less than 10^6. There are 6944 multiples of 144 in that range.
ReplyDeleteYes. Oops. I mistyped. Since latex doesn't render, here's a viewable version
ReplyDeleteto really weed out the people who did not actually know how to intelligently count
ReplyDeleteYou could still brute force up to $999$ :P