2018 AIME II Problems/Problem 15
Problem
Find the number of functions from
to the integers such that
,
, and
for all and
in
.
Solution
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.
-kgator
2018 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 14 |
Followed by Last question | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.