Maths Olympiad Prep

Library / /1197 of 1394

, 2016

Combinatorics Difficulty 5.8 AIME, harder Prove it United States

Problem:
Let XX be the collection of all functions f:{0,1,,2016}{0,1,,2016}f:\{0,1, \ldots, 2016\} \rightarrow \{0,1, \ldots, 2016\}. Compute the number of functions fXf \in X such that
maxgX(min0i2016(max(f(i),g(i)))max0i2016(min(f(i),g(i))))=2015. \max _{g \in X}\left(\min _{0 \leq i \leq 2016}(\max (f(i), g(i)))-\max _{0 \leq i \leq 2016}(\min (f(i), g(i)))\right)=2015 .
Proposed by:

Solution

Solution:
For each f,gXf, g \in X, we define
d(f,g):=min0i2016(max(f(i),g(i)))max0i2016(min(f(i),g(i))) d(f, g):=\min _{0 \leq i \leq 2016}(\max (f(i), g(i)))-\max _{0 \leq i \leq 2016}(\min (f(i), g(i)))
Thus we desire maxgXd(f,g)=2015\max _{g \in X} d(f, g)=2015.

First, we count the number of functions fXf \in X such that
g:minimax{f(i),g(i)}2015 and g:minimax{f(i),g(i)}=0. \exists g: \min _{i} \max \{f(i), g(i)\} \geq 2015 \text{ and } \exists g: \min _{i} \max \{f(i), g(i)\}=0 .
That means for every value of ii, either f(i)=0f(i)=0 (then we pick g(i)=2015g(i)=2015) or f(i)2015f(i) \geq 2015 (then we pick g(i)=0g(i)=0). So there are A=32017A=3^{2017} functions in this case.

Similarly, the number of functions such that
g:minimax{f(i),g(i)}=2016 and g:minimax{f(i),g(i)}1 \exists g: \min _{i} \max \{f(i), g(i)\}=2016 \text{ and } \exists g: \min _{i} \max \{f(i), g(i)\} \leq 1
is also B=32017B=3^{2017}.

Finally, the number of functions such that
g:minimax{f(i),g(i)}=2016 and g:minimax{f(i),g(i)}=0 \exists g: \min _{i} \max \{f(i), g(i)\}=2016 \text{ and } \exists g: \min _{i} \max \{f(i), g(i)\}=0
is C=22017C=2^{2017}.

Now A+BCA+B-C counts the number of functions with maxgXd(f,g)2015\max _{g \in X} d(f, g) \geq 2015 and CC counts the number of functions with maxgXd(f,g)2016\max _{g \in X} d(f, g) \geq 2016, so the answer is A+B2C=2(3201722017)A+B-2C=2 \cdot\left(3^{2017}-2^{2017}\right).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.