HMMT 二月 2012 · TEAM1 赛 · 第 8 题

英文解析

8. [ 30 ] For integer n, m ≥ 1, let A ( n, m ) denote the number of functions f : { 1 , 2 , . . . , n } → { 1 , 2 , . . . , m }
   such that f ( j ) − f ( i ) ≤ j − i for all 1 ≤ i < j ≤ n , and let B ( n, m ) denote the number of functionsg : { 0 , 1 , . . . , 2 n + m } → { 0 , 1 , . . . , m } such that g (0) = 0, g (2 n + m ) = m , and | g ( i ) − g ( i − 1) | = 1 forall 1 ≤ i ≤ 2 n + m . Prove that A ( n, m ) = B ( n, m ).
   Team A
   Answer: see below We first note that the condition for f is equivalent to i − f ( i ) ≤ j − f ( j ) for
   ′ ′
   all 1 ≤ i < j ≤ n . Letting f ( x ) = x − f ( x ), we see this is equivalent to saying that f is decreasing.
   ′ ′
   Thus, we only need that f ( x ) ≤ f ( x + 1); in other words, we only require the statement to be truefor j = i + 1.
   Fix m, n . For any function g satisfying the conditions for B , we construct a function f satisfying theconditions for A as follows. For a given function g and 1 ≤ i ≤ 2 n + m , say that g has a up step at i ifg ( i ) − g ( i − 1) = 1, and say it has a down step at i otherwise. We see that g must be composed of m + nup steps and n down steps. Let i , i , . . . , i be the indices for which down steps occur, in ascending
   1 2 norder. Let f be the function such that f ( j ) = ( m + 1) − g ( i ) for 1 ≤ j ≤ n . By our argument in the first paragraph, it suffices to show that f ( k ) − f ( k − 1) ≤ 1 for 1 < k ≤ n , or that g ( i ) − 1 ≤ g ( i ).jk − 1 k
   If this were not the case for some k , then there would be at least 1 down step in between i and i ,
   k − 1 ka contradiction, so the condition indeed holds.
   We now claim that this construction is a bijection. For injectivity, note that for any two distinct
   ′ ′ ′
   g, g , there exists a k for which the values of g ( i ) , g ( i ) are distinct, in which case the functionsk
   ′ ′kf, f must be distinct. For surjectivity, consider any suitable f . Let f be the function such that
   ′
   f ( k ) = ( m + 1) − f ( k ) for all 1 ≤ k ≤ n . (The range of this function is still { 1 , 2 , . . . , m } .) Then, wecan find a g as follows: for each 1 ≤ k ≤ n in sequence, have g make up steps until it reaches the value
   ′ ′ ′
   f ( k ), then take one down step. This is always possible, as f ( k + 1) − f ( k ) ≤ 1. Thus, our claim istrue, and our proof is complete.