2021 AIME II Problems/Problem 15
Let and be functions satisfying and for positive integers . Find the least positive integer such that .
Consider what happens when we try to calculate where n is not a square. If for (positive) integer k, recursively calculating the value of the function gives us . Note that this formula also returns the correct value when , but not when . Thus for .
If , returns the same value as . This is because the recursion once again stops at . We seek a case in which , so obviously this is not what we want. We want to have a different parity, or have the same parity. When this is the case, instead returns .
Write , which simplifies to . Notice that we want the expression to be divisible by 3; as a result, . We also want n to be strictly greater than , so . The LHS expression is always even (why?), so to ensure that k and n share the same parity, k should be even. Then the least k that satisfies these requirements is , giving .
Indeed - if we check our answer, it works. Therefore, the answer is .
Solution 2 (Four Variables)
We consider and separately:
We restrict in which for some positive integer or for some integer such that By recursion, we get
If and have the same parity, then starting from we get by a similar process. This contradicts the precondition Therefore, and must have different parities, from which and must have the same parity.
It follows that or for some integer such that By recursion, we get
By and we have From and equating the expressions for gives Solving for produces We substitute into then simplify, cross-multiply, and rearrange: Since we know that must be divisible by and must be divisible by
Recall that the restrictions on and are and respectively. Substituting into either inequality gives Combining all these results produces To minimize in either or we minimize so we minimize and in From and we construct the following table: Finally, we have Substituting this result into either or generates
We can verify that
Since isn't a perfect square, let with . If is odd, then . If is even, Since is even, is even. Since , the smallest is which produces the smallest .
To begin, note that if is a perfect square, , so , so we must look at values of that are not perfect squares (what a surprise). First, let the distance between and the first perfect square greater than or equal to it be , making the values of and integers. Using this notation, we see than , giving us a formula for the numerator of our ratio. However, since the function of does not add one to the previous inputs in the function until a perfect square is achieved, but adds values of two, we can not achieve the value of in unless is an even number. However, this is impossible, since if was an even number, , giving a ratio of one. Thus, must be an odd number.
Thus, since must be an odd number, regardless of whether is even or odd, to get an integral value in , we must get to the next perfect square after . To make matters easier, let . Thus, in , we want to achieve .
Expanding and substituting in the fact that yields:
Thus, we must add the quantity to to achieve a integral value in the function . Thus.
|2021 AIME II (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|