Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2018 AIME II Problems/Problem 15"

(→‎Solution)
m (→‎Solution)
Line 19: Line 19:
 
is always true. We now have two cases of functions to count. For future reference let <math>D</math> be the (ordered) sequence <math>\left\{d_1, d_2, d_3, d_4, d_5, d_6\right\}</math>.
 
is always true. We now have two cases of functions to count. For future reference let <math>D</math> be the (ordered) sequence <math>\left\{d_1, d_2, d_3, d_4, d_5, d_6\right\}</math>.
  
−
Case 1: There is exactly one instance of <math>d_k = -1</math>.
+
[b]Case 1:[/b] There is exactly one instance of <math>d_k = -1</math>.
  
 
By the "stronger" inequality above, <math>d_{k-1} = 3</math> if <math>k > 1</math>, and <math>d_{k+1} = 3</math> if <math>k < 6</math>. If <math>2 \leq k \leq 5</math>, then <math>D</math> contains the subsequence <math>\left\{3, -1, 3\right\}</math>, and the other three <math>d</math>-values sum to <math>7</math>, so they are either <math>3</math>, <math>3</math>, and <math>1</math> in some order, or they are <math>2</math>, <math>2</math>, and <math>3</math> in some order. Thus, each <math>k \in \{2, 3, 4, 5\}</math> for which <math>d_k = -1</math> produces <math>6</math> sequences <math>D</math>. If <math>k = 1</math> or <math>k = 6</math>, then <math>D</math> begins with <math>\{-1, 3\}</math> or ends with <math>\{3, -1\}</math>, respectively. Either way, the remaining four <math>d</math>-values sum to <math>10</math>, so they can be any permutation of <math>\{3, 3, 2, 2\}</math> (six permutations) or <math>\{3, 3, 3, 1\}</math> (four permutations). Each of these vaues of <math>k</math> yields <math>6 + 4 = 10</math> sequences, so our total count for Case 1 is <math>4 \cdot 6 + 2 \cdot 10 = 44</math>.
 
By the "stronger" inequality above, <math>d_{k-1} = 3</math> if <math>k > 1</math>, and <math>d_{k+1} = 3</math> if <math>k < 6</math>. If <math>2 \leq k \leq 5</math>, then <math>D</math> contains the subsequence <math>\left\{3, -1, 3\right\}</math>, and the other three <math>d</math>-values sum to <math>7</math>, so they are either <math>3</math>, <math>3</math>, and <math>1</math> in some order, or they are <math>2</math>, <math>2</math>, and <math>3</math> in some order. Thus, each <math>k \in \{2, 3, 4, 5\}</math> for which <math>d_k = -1</math> produces <math>6</math> sequences <math>D</math>. If <math>k = 1</math> or <math>k = 6</math>, then <math>D</math> begins with <math>\{-1, 3\}</math> or ends with <math>\{3, -1\}</math>, respectively. Either way, the remaining four <math>d</math>-values sum to <math>10</math>, so they can be any permutation of <math>\{3, 3, 2, 2\}</math> (six permutations) or <math>\{3, 3, 3, 1\}</math> (four permutations). Each of these vaues of <math>k</math> yields <math>6 + 4 = 10</math> sequences, so our total count for Case 1 is <math>4 \cdot 6 + 2 \cdot 10 = 44</math>.
  
−
Case 2: All values of <math>d</math> are positive.
+
[b]Case 2:[/b] All values of <math>d</math> are positive.
  
 
Then, <math>D</math> is a permutation of <math>\{3, 3, 3, 1, 1, 1\}</math>, <math>\{3, 3, 2, 2, 1, 1\}</math>, <math>\{3, 2, 2, 2, 2, 1\}</math>, or <math>\{2, 2, 2, 2, 2, 2\}</math>.
 
Then, <math>D</math> is a permutation of <math>\{3, 3, 3, 1, 1, 1\}</math>, <math>\{3, 3, 2, 2, 1, 1\}</math>, <math>\{3, 2, 2, 2, 2, 1\}</math>, or <math>\{2, 2, 2, 2, 2, 2\}</math>.
Line 35: Line 35:
 
<math>x - y \leq f(x) - f(y) \leq 3(x - y).</math>
 
<math>x - y \leq f(x) - f(y) \leq 3(x - y).</math>
  
−
Now, the inequality is transitive; supposing <math>a \leq x_3 < x_2 < x_1 \leq b</math>, if the inequality is satisfied at <math>(x, y) = \left(x_1, x_2\right)</math> and at <math>(x, y) = \left(x_2, x_3\right)</math>, then it is also satisfied at <math>(x, y) = \left(x_1, x_3\right)</math>. If we ever have a decreasing part where <math>f(x + 1) < f(x)</math>, then we can use some variant of the inequality <math>2 \leq f(x + 1) - f(x - 1) \leq 6</math>, which we derived earlier. This is a specific case of <math>x - y \leq f(x) - f(y) \leq 3(x - y)</math>, so we can finish off the argument by invoking transitivity.    -kgator
+
Now, the inequality is transitive; supposing <math>a \leq x_3 < x_2 < x_1 \leq b</math>, if the inequality is satisfied at <math>(x, y) = \left(x_1, x_2\right)</math> and at <math>(x, y) = \left(x_2, x_3\right)</math>, then it is also satisfied at <math>(x, y) = \left(x_1, x_3\right)</math>. If we ever have a decreasing part where <math>f(x + 1) < f(x)</math>, then we can use some variant of the inequality <math>2 \leq f(x + 1) - f(x - 1) \leq 6</math>, which we derived earlier. This is a specific case of <math>x - y \leq f(x) - f(y) \leq 3(x - y)</math>, so we can finish off the argument by invoking transitivity.     
 +
 
 +
-kgator
  
  

Revision as of 22:53, 23 February 2019

Problem

Find the number of functions $f$ from $\{0, 1, 2, 3, 4, 5, 6\}$ to the integers such that $f(0) = 0$, $f(6) = 12$, and

$|x - y|$ $\leq$ $|f(x) - f(y)|$ $\leq$ $3|x - y|$

for all $x$ and $y$ in $\{0, 1, 2, 3, 4, 5, 6\}$.

Solution

First, suppose $x = y + 1$. Then, the inequality becomes $1 \leq |f(y + 1) - f(y)| \leq 3$. In other words, the (positive) difference between consecutive function values is $1$, $2$, or $3$. Let $d_k := f(k) - f(k - 1)$. Note that

$f(x) - f(y) = \sum_{k=y+1}^{x} d_k.$

Thus, $\sum_{k=1}^{6} d_k = f(6) - f(0) = 12$. Note that at most one value of $d_k$ in $\left\{d_1, d_2, d_3, d_4, d_5, d_6\right\}$ can be negative. This is because the maximum value of $d_1 + d_2 + d_3 + d_4 + d_5 + d_6$ would be $3 + 3 + 3 + 3 - 1 - 1 = 10$ if more than one value of $d_k$ is negative. Plugging $x = y + 2$ into the original inequality yields $2 \leq |f(y + 2) - f(y)| \leq 6$, which becomes $2 \leq \left|d_{y+2} + d_{y+1}\right| \leq 6$. The only way for $d_{y+2} + d_{y+1}$ to be negative while satisfying this inequality is for $\left(d_{y+2}, d_{y+1}\right)$ to equal $(1, -3)$ or $(-3, 1)$. However, this forces $d_1 + d_2 + d_3 + d_4 + d_5 + d_6 \leq 3 + 3 + 3 + 3 + 1 - 3 = 10 < 12$, which is disallowed. Hence, we conclude that the following stronger inequality,

$2 \leq d_{y + 2} + d_{y + 1} \leq 6,$

is always true. We now have two cases of functions to count. For future reference let $D$ be the (ordered) sequence $\left\{d_1, d_2, d_3, d_4, d_5, d_6\right\}$.

[b]Case 1:[/b] There is exactly one instance of $d_k = -1$.

By the "stronger" inequality above, $d_{k-1} = 3$ if $k > 1$, and $d_{k+1} = 3$ if $k < 6$. If $2 \leq k \leq 5$, then $D$ contains the subsequence $\left\{3, -1, 3\right\}$, and the other three $d$-values sum to $7$, so they are either $3$, $3$, and $1$ in some order, or they are $2$, $2$, and $3$ in some order. Thus, each $k \in \{2, 3, 4, 5\}$ for which $d_k = -1$ produces $6$ sequences $D$. If $k = 1$ or $k = 6$, then $D$ begins with $\{-1, 3\}$ or ends with $\{3, -1\}$, respectively. Either way, the remaining four $d$-values sum to $10$, so they can be any permutation of $\{3, 3, 2, 2\}$ (six permutations) or $\{3, 3, 3, 1\}$ (four permutations). Each of these vaues of $k$ yields $6 + 4 = 10$ sequences, so our total count for Case 1 is $4 \cdot 6 + 2 \cdot 10 = 44$.

[b]Case 2:[/b] All values of $d$ are positive.

Then, $D$ is a permutation of $\{3, 3, 3, 1, 1, 1\}$, $\{3, 3, 2, 2, 1, 1\}$, $\{3, 2, 2, 2, 2, 1\}$, or $\{2, 2, 2, 2, 2, 2\}$. The number of ways to permute three $3$s and three $1$s is $\frac{6!}{3! \cdot 3!} = 20$. The number of ways to permute two $3$s, two $2$s, and two $1$s is $\frac{6!}{2! \cdot 2! \cdot 2!} = 90$. The number of ways to permute one $3$, four $2$s, and one $1$ is $\frac{6!}{1! \cdot 4! \cdot 1!} = 30$. Finally, there is obviously only $1$ way to permute six $2$s. Our total count for Case 2 is $20 + 90 + 30 + 1 = 141$.

To complete the justification that all of these $44 + 141 = \boxed{185}$ cases satisfy the original inequality, we leverage the fact that $\{f(x)\}_{x=0}^{6}$ is either monotonically increasing (Case 2) or the union of two monotonically increasing subsequences (Case 1). Consider any monotonically increasing subsequence that starts at $x = a$ and ends at $x = b$. For $a < k \leq b$, $d_k$ will be positive, allowing us to remove the absolute value bars from the original inequality:

$x - y \leq f(x) - f(y) \leq 3(x - y).$

Now, the inequality is transitive; supposing $a \leq x_3 < x_2 < x_1 \leq b$, if the inequality is satisfied at $(x, y) = \left(x_1, x_2\right)$ and at $(x, y) = \left(x_2, x_3\right)$, then it is also satisfied at $(x, y) = \left(x_1, x_3\right)$. If we ever have a decreasing part where $f(x + 1) < f(x)$, then we can use some variant of the inequality $2 \leq f(x + 1) - f(x - 1) \leq 6$, which we derived earlier. This is a specific case of $x - y \leq f(x) - f(y) \leq 3(x - y)$, 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_AIME_II_Problems/Problem_15&oldid=103794"