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 , or to the closest point with a greater integer coordinate that is a multiple of . A move sequence is a sequence of coordinates which correspond to valid moves, beginning with , and ending with . For example, is a move sequence. How many move sequences are possible for the frog?
Solution: Let be the number of possible move sequences starting from and ending up at . Clearly it is only interesting when is divisible by or . So let’s try to construct the sequence.
is our base case. There is only one way to get to the value from , so . Similarly, , , and . But how many ways can we get to ? Well, if we start at any of the previously mentioned numbers there we can go straight to from them (by using the next multiple of move). So
Now how about ? Well we can get there from either or , so
Continuing, we have because we can only get to these from the previous multiples of . Then
In this similar fashion, we obtain and finally . QED.
Comment: This is a cool problem, though they could have made it harder to brute force (i.e. have the answer be ) 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 to calculate .
Practice Problem: (2007 AIMEI – #1) How many positive perfect squares less than are multiples of ?
Leave a Reply
You must be logged in to post a comment.