Difference between revisions of "2018 AIME II Problems/Problem 15"
(→Problem) |
|||
(2 intermediate revisions by the same user not shown) | |||
Line 2: | Line 2: | ||
Find the number of functions <math>f</math> from <math>\{0, 1, 2, 3, 4, 5, 6\}</math> to the integers such that <math>f(0) = 0</math>, <math>f(6) = 12</math>, and | Find the number of functions <math>f</math> from <math>\{0, 1, 2, 3, 4, 5, 6\}</math> to the integers such that <math>f(0) = 0</math>, <math>f(6) = 12</math>, and | ||
+ | <cmath>|x - y| \leq |f(x) - f(y)| \leq 3|x - y|</cmath> | ||
+ | for all <math>x</math> and <math>y</math> in <math>\{0, 1, 2, 3, 4, 5, 6\}</math>. | ||
+ | |||
+ | ==Official Solution (MAA)== | ||
+ | |||
+ | Because <math>f(n)</math> and <math>f(n+1)</math> can differ by at most 3 for <math>n=0,1,2,3,4,5</math>, <math>f</math> can decrease at most once. This is because if <math>f</math> decreases <math>2</math> times (or more) then we get a contradiction: <math>12 = f(6) \le 3\cdot 4 + (-1)\cdot 2 = 10</math>. | ||
− | <math> | + | If <math>f</math> never decreases, then <math>f(n+1)-f(n)\in \{1,2,3\}</math> for all <math>n</math>. Let <math>a, b</math>, and <math>c</math> denote the number of times this difference is <math>1, 2</math>, and <math>3</math>, respectively. Then <math>a+b+c=6</math> and <math>a+2b+3c = 12</math>. Subtracting the first equation from the second yields <math>b+2c=6</math>, so <math>(b,c)=(6,0), (4,1), (2,2)</math>, or <math>(0,3)</math>. These yield <math>a=0,1,2</math>, or <math>3</math>, respectively, so the number of possibilities in this case is<cmath>\binom{6}{0,6,0}+\binom{6}{1,4,1}+\binom{6}{2,2,2}+\binom{6}{3,0,3}=141.</cmath>If <math>f</math> decreases from <math>f(0)</math> to <math>f(1)</math> or from <math>f(5)</math> to <math>f(6)</math>, then <math>f(2)</math> or <math>f(4)</math>, respectively, is determined. The only solutions to <math>a+b+c=4</math> and <math>a+2b+3c=10</math> are <math>(a,b,c)=(1,0,3)</math> and <math>(a,b,c)=(0,2,2)</math>, so the number of functions is <cmath>2\left[\binom{4}{1,0,3}+\binom{4}{0,2,2}\right]=20. </cmath>Finally, suppose that <math>f(n+1)<f(n)</math> for some <math>n=1,2,3,4</math>. Note that the condition <math>|(n+1)-(n-1)|\le |f(n+1)-f(n-1)|</math> implies that <math>f(n+1)-f(n-1)\ge 2</math>, so it must be that <math>f(n)-f(n+1)=1</math> and <cmath>f(n+2)-f(n+1)=f(n)-f(n-1)=3.</cmath>This means that <math>f(n-1)</math> and <math>f(n+2)</math> are uniquely determined by the value of <math>f(n)</math>, and, in particular, that <math>f(n+2)-f(n-1)=5</math>. As a result, there are three more values of <math>f</math> to determine, and they must provide a total increase of <math>7</math>. The only ways to do this are either to have two differences of <math>3</math> and one difference of <math>1</math>, which can be arranged in <math>3</math> ways, or to have one difference of <math>3</math> and two differences of <math>2</math>, which can be arranged in <math>3</math> ways. Thus for each of the <math>4</math> possibilities for <math>n</math>, there are <math>6</math> ways to arrange the increases, giving a total of <math>24</math> ways. |
+ | |||
+ | The total number of functions is <math>141+20+24=\boxed{185}</math>. | ||
− | |||
==Solution 1== | ==Solution 1== |
Latest revision as of 10:27, 4 February 2022
Problem
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 is
If
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 .
Solution 1
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
Solution 2
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
.
-mathdummy
See Also
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.