Maths Olympiad Prep

Library / /538 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

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)=0)g(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-2 C=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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.