2010 AIME I Problems/Problem 10
Let be the number of ways to write in the form , where the 's are integers, and . An example of such a representation is . Find .
If we choose and such that there is a unique choice of and that makes the equality hold. So is just the number of combinations of and we can pick. If or we can let be anything from to . If then or . Thus .
Note that is the base representation of any number from to , and similarly is ten times the base representation of any number from to . Thus, the number of solutions is just the number of solutions to where , which is equal to as can range from to .
Note that and . It's easy to see that exactly 10 values in that satisfy our first congruence. Similarly, there are 10 possible values of for each choice of . Thus, there are possible choices for and . We next note that if and are chosen, then a valid value of determines , so we dive into some simple casework:
- If , there are 3 valid choices for . There are only 2 possible cases where , namely . Thus, there are possible representations in this case.
- If , can only equal 0. However, this case cannot occur, as . Thus, . However, . Thus, we have always.
- If , then there are 2 valid choices for . Since there are 100 possible choices for and , and we have already checked the other cases, it follows that choices of and fall under this case. Thus, there are possible representations in this case.
Our answer is thus .
Solution 4: Casework and Brute Force
We immediately see that can only be , or . We also note that the maximum possible value for is . We then split into cases:
Case 1: . We try to find possible values of . We plug in and to our initial equation, which gives us . Thus . We also see that . We now take these values of and find the number of pairs that work. If , . We see that there are possible pairs in this case. Using the same logic, there are ways for . For , we get the equation , for 2 ways. Thus, for , there are ways.
Case 2: . This case is almost identical to the one above, except . We also get 100 ways.
Case 3: . If , our initial equation becomes . It is obvious that , and we are left with . We saw above that there are ways.
Totaling everything, we get that there are ways.
Solution 5: Generating Functions
We will represent the problem using generating functions. Consider the generating function where the first factor represents , the second factor , and so forth. We want to find the coefficient of in the expansion of . Now rewriting each factor using the geometric series yields The coefficient of in this is simply , as we can choose any of the first 202 terms from the second factor and pair it with exactly one term in the first factor.
|2010 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|