2018 AIME II Problems/Problem 15
Find the number of functions from to the integers such that , , and for all and in .
Official Solution (MAA)
Because and can differ by at most 3 for , can decrease at most once. This is because if decreases times (or more) then we get a contradiction: .
If never decreases, then for all . Let , and denote the number of times this difference is , and , respectively. Then and . Subtracting the first equation from the second yields , so , or . These yield , or , respectively, so the number of possibilities in this case isIf decreases from to or from to , then or , respectively, is determined. The only solutions to and are and , so the number of functions is Finally, suppose that for some . Note that the condition implies that , so it must be that and This means that and are uniquely determined by the value of , and, in particular, that . As a result, there are three more values of to determine, and they must provide a total increase of . The only ways to do this are either to have two differences of and one difference of , which can be arranged in ways, or to have one difference of and two differences of , which can be arranged in ways. Thus for each of the possibilities for , there are ways to arrange the increases, giving a total of ways.
The total number of functions is .
First, suppose . Then, the inequality becomes . In other words, the (positive) difference between consecutive function values is , , or . Let . Note that
Thus, . Note that at most one value of in can be negative. This is because the maximum value of would be if more than one value of is negative. Plugging into the original inequality yields , which becomes . The only way for to be negative while satisfying this inequality is for to equal or . However, this forces , which is disallowed. Hence, we conclude that the following stronger inequality,
is always true. We now have two cases of functions to count. For future reference let be the (ordered) sequence .
Case 1: There is exactly one instance of .
By the "stronger" inequality above, if , and if . If , then contains the subsequence , and the other three -values sum to , so they are either , , and in some order, or they are , , and in some order. Thus, each for which produces sequences . If or , then begins with or ends with , respectively. Either way, the remaining four -values sum to , so they can be any permutation of (six permutations) or (four permutations). Each of these vaues of yields sequences, so our total count for Case 1 is .
Case 2: All values of are positive.
Then, is a permutation of , , , or . The number of ways to permute three s and three s is . The number of ways to permute two s, two s, and two s is . The number of ways to permute one , four s, and one is . Finally, there is obviously only way to permute six s. Our total count for Case 2 is .
To complete the justification that all of these cases satisfy the original inequality, we leverage the fact that is either monotonically increasing (Case 2) or the union of two monotonically increasing subsequences (Case 1). Consider any monotonically increasing subsequence that starts at and ends at . For , will be positive, allowing us to remove the absolute value bars from the original inequality:
Now, the inequality is transitive; supposing , if the inequality is satisfied at and at , then it is also satisfied at . If we ever have a decreasing part where , then we can use some variant of the inequality , which we derived earlier. This is a specific case of , so we can finish off the argument by invoking transitivity.
Based on the conditions for obtained in Solution 1, followed by some well-known stars & bars techniques to reduce the case work. To recap, the conditions for are:
Case 1: for some . Since , and must both be 3.
Case 1a: or . In this case, we have or , respectively. So the remaining four values add up to 10 with each value ranging between 1 and 3. This stars and bars problem is equivalent to with between 0 and 2, so the number of possibilities is each.
Case 1b: for . In this case, . So the remaining 3 values add up to 7 with each value ranging between 1 and 3. This stars and bars problem is equivalent to with between 0 and 2, so the number of possibilities is each.
So the total for Case 1 is .
Case 2: for all . . Let we get for . This is a stars and bars problem with maximum capacity and the solution is given by applying PIE: . Now the final answer is .
|2018 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|