2016 AMC 12B Problems/Problem 25
Contents
Problem
The sequence is defined recursively by , , and for . What is the smallest positive integer such that the product is an integer?
Solution 1
Let . Then and for all . The characteristic polynomial of this linear recurrence is , which has roots and .
Therefore, for constants to be determined . Using the fact that we can solve a pair of linear equations for :
.
Thus , , and .
Now, , so we are looking for the least value of so that
.
Note that we can multiply all by three for convenience, as the are always integers, and it does not affect divisibility by .
Now, for all even the sum (adjusted by a factor of three) is . The smallest for which this is a multiple of is by Fermat's Little Theorem, as it is seen with further testing that is a primitive root .
Now, assume is odd. Then the sum (again adjusted by a factor of three) is . The smallest for which this is a multiple of is , by the same reasons. Thus, the minimal value of is .
Solution 2
Since the product is an integer, the sum of the logarithms must be an integer. Multiply all of these logarithms by , so that the sum must be a multiple of . We take these vales modulo to save calculation time. Using the recursion : Notice that . The cycle repeats every terms. Since and , we only need the first terms to sum up to a multiple of : . (NOTE: This solution proves 17 is the upper bound, but since 17 is the lowest answer choice, it is correct. To rigorously prove it, you will have to add up the mods listed until you get .
See Also
2016 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 24 |
Followed by Last Problem |
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.