2015 AIME I Problems/Problem 14
For each integer , let be the area of the region in the coordinate plane defined by the inequalities and , where is the greatest integer not exceeding . Find the number of values of with for which is an integer.
Let and define . For , we have .
For we have . Thus (say), and is an integer if is even; otherwise is an integer plus .
If , and is of the form so is an integer when is even.
If , and is an integer for all . Since is not an integer, so is not an integer for any .
If , and is of the form . Since is of the form so is an integer only when is odd.
If , and is an integer for all . Since is an integer so is an integer for all .
Now we are back to where we started; i.e., the case will be the same as and so on. Thus,
For each there are corresponding values of : i.e., .
Thus, the number of values of corresponding to (i.e., ) is given by
The cases and combine to account for half the values of corresponding to odd values of ; i.e., However, this also includes the odd integers in . Subtracting to account for these, we get the number of values of corresponding to cases and to be .
Adding the contributions from all cases we get our answer to be .
By considering the graph of this function, it is shown that the graph is composed of trapezoids ranging from to with the top made of diagonal line . The width of each trapezoid is , etc. Whenever is odd, the value of increases by an integer value, plus . Whenever is even, the value of increases by an integer value. Since each trapezoid always has an odd width, every value of is not an integer when , and is an integer when . Every other value is an integer when is odd. Therefore, it is simply a matter of determining the number of values of where (), and adding the number of values of where is odd (). Adding the two values gives .
First, draw a graph of the function. Note that it is just a bunch of line segments. Since we only need to know whether or not is an integer, we can take the area of each piece from some to (mod 1), aka the piece from to has area . There are some patterns. Every time we increase starting with , we either add or . We look at for inspiration. Every time this floor (which is really the slope) is odd, there is always an addition of , and whenever that slope is even, that addition is zero.
Take a few cases. For slope , we see that only one value satisfies. Because the last value, , fails, and the numbers which have a slope of an even number don't change this modulus, all these do not satisfy the criterion. The pattern then comes back to the odds, and this time values work. Since the work/fail pattern alternates, all the s with even slope, , satisfy the criterion. This pattern is cyclic over period 4 of slopes.
Even summation of working cases: . Odd summation: and plus the cases from : . Answer is .
|2015 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|