HMMT 二月 2016 · COMB 赛 · 第 8 题

英文解析

8. Let X be the collection of all functions f : { 0 , 1 , . . . , 2016 } → { 0 , 1 , . . . , 2016 } . Compute the numberof functions f ∈ X such that
   ( )
   ( ) ( )
   max min max( f ( i ) , g ( i )) − max min( f ( i ) , g ( i )) = 2015 .
   g ∈ X 0 ≤ i ≤ 2016 0 ≤ i ≤ 2016
   Proposed by:
   2017 2017
   Answer: 2 · (3 − 2 )
   For each f, g ∈ X , we define
   ( ) ( )
   d ( f, g ) := min max( f ( i ) , g ( i )) − max min( f ( i ) , g ( i ))
   0 ≤ i ≤ 2016 0 ≤ i ≤ 2016
   Thus we desire max d ( f, g ) = 2015.
   g ∈ X
   First, we count the number of functions f ∈ X such that
   ∃ g : min max { f ( i ) , g ( i ) } ≥ 2015 and ∃ g : min max { f ( i ) , g ( i ) } = 0 .
   i i
   That means for every value of i , either f ( i ) = 0 (then we pick g ( i ) = 2015) or f ( i ) ≥ 2015 (then we
   2017
   pick g ( i ) = 0). So there are A = 3 functions in this case.
   Similarly, the number of functions such that
   ∃ g : min max { f ( i ) , g ( i ) } = 2016 and ∃ g : min max { f ( i ) , g ( i ) } ≤ 1
   i i
   2017
   is also B = 3 .
   Finally, the number of functions such that
   ∃ g : min max { f ( i ) , g ( i ) } = 2016 and ∃ g : min max { f ( i ) , g ( i ) } = 0
   i i
   2017
   is C = 2 .
   Now A + B − C counts the number of functions with max d ( f, g ) ≥ 2015 and C counts the numberg ∈ X
   2017 2017
   of functions with max d ( f, g ) ≥ 2016, so the answer is A + B − 2 C = 2 · (3 − 2 ).
   g ∈ X