# Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.

• ## Meta

Frogger. Topic: Combinatorics. Level: AIME. March 17th, 2007

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 ?

### 4 Responses to “Frogger. Topic: Combinatorics. Level: AIME.”

1. #H34N1 Says:

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$.

2. t0rajir0u Says:

You mean there are 83 square multiples of 144 less than 10^6. There are 6944 multiples of 144 in that range.

3. #H34N1 Says:

Yes. Oops. I mistyped. Since latex doesn’t render, here’s a viewable version

4. #H34N1 Says:

to really weed out the people who did not actually know how to intelligently count

You could still brute force up to $$999$$