HMMT 二月 2012 · TEAM1 赛 · 第 8 题
HMMT February 2012 — TEAM1 Round — Problem 8
题目详情
- [ 30 ] For integer m, n ≥ 1, let A ( m, n ) 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 ( m, n ) denote the number of functions g : { 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 for all 1 ≤ i ≤ 2 n + m . Prove that A ( m, n ) = B ( m, n ). For the remaining problems, let ϕ ( k ) denote the number of positive integers less than or equal to k that are relatively prime to k .
解析
- [ 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 functions g : { 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 for all 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 true for j = i + 1. Fix m, n . For any function g satisfying the conditions for B , we construct a function f satisfying the conditions for A as follows. For a given function g and 1 ≤ i ≤ 2 n + m , say that g has a up step at i if g ( i ) − g ( i − 1) = 1, and say it has a down step at i otherwise. We see that g must be composed of m + n up steps and n down steps. Let i , i , . . . , i be the indices for which down steps occur, in ascending 1 2 n order. Let f be the function such that f ( j ) = ( m + 1) − g ( i ) for 1 ≤ j ≤ n . By our argument in the j first paragraph, it suffices to show that f ( k ) − f ( k − 1) ≤ 1 for 1 < k ≤ n , or that g ( i ) − 1 ≤ g ( i ). k − 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 k a 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 functions k k ′ ′ f, 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, we can 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 is true, and our proof is complete.