2006 AMC 12B Problems/Problem 22
Suppose , and are positive integers with , and , where and are integers and is not divisible by . What is the smallest possible value of ?
The power of for any factorial is given by the well-known algorithm It is rational to guess numbers right before powers of because we won't have any extra numbers from higher powers of . As we list out the powers of 5, it is clear that is less than 2006 and is greater. Therefore, set and to be 624. Thus, c is . Applying the algorithm, we see that our answer is .
Clearly, the power of that divides is larger or equal than the power of which divides it. Hence we are trying to minimize the power of that will divide .
Consider . Each fifth term is divisible by , each -th one by , and so on. Hence the total power of that divides is . (For any only finitely many terms in the sum are non-zero.)
In our case we have , so the largest power of that will be less than is at most . Therefore the power of that divides is equal to . The same is true for and .
Intuition may now try to lure us to split into as evenly as possible, giving and . However, this solution is not optimal.
To see how we can do better, let's rearrange the terms as follows:
The idea is that the rows of the above equation are roughly equal to , , etc.
More precisely, we can now notice that for any positive integers we can write in the form , , , where all are integers and .
It follows that and
Hence we get that for any positive integers we have
Therefore for any the result is at least .
If we now show how to pick so that we'll get the result , we will be done.
Consider the row with in the denominator. We need to achieve sum in this row, hence we need to make two of the numbers smaller than . Choosing does this, and it will give us the largest possible remainders for and in the other three rows, so this is a pretty good candidate. We can compute and verify that this triple gives the desired result .
|2006 AMC 12B (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25|
|All AMC 12 Problems and Solutions|