HMMT 二月 2016 · COMB 赛 · 第 8 题

HMMT February 2016 — COMB Round — Problem 8

Let X be the collection of all functions f : { 0 , 1 , . . . , 2016 } → { 0 , 1 , . . . , 2016 } . Compute the number of 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

解析

Let X be the collection of all functions f : { 0 , 1 , . . . , 2016 } → { 0 , 1 , . . . , 2016 } . Compute the number of 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 number g ∈ X 2017 2017 of functions with max d ( f, g ) ≥ 2016, so the answer is A + B − 2 C = 2 · (3 − 2 ). g ∈ X