HMMT 二月 2011 · ALGCOMB 赛 · 第 16 题
HMMT February 2011 — ALGCOMB Round — Problem 16
题目详情
- Let A = { 1 , 2 , . . . , 2011 } . Find the number of functions f from A to A that satisfy f ( n ) ≤ n for all n in A and attain exactly 2010 distinct values. 2 π 2 π
解析
- Let A = { 1 , 2 , . . . , 2011 } . Find the number of functions f from A to A that satisfy f ( n ) ≤ n for all n in A and attain exactly 2010 distinct values. 2011 Answer: 2 − 2012 Let n be the element of A not in the range of f . Let m be the element of A that is hit twice. Algebra & Combinatorics Individual Test We now sum the total number of functions over n, m . Clearly f (1) = 1, and by induction, for x ≤ m, f ( x ) = x . Also unless n = 2011, f (2011) = 2011 because f can take no other number to 2011. It follows from backwards induction that for x > n , f ( x ) = x . Therefore n > m , and there are only n − m values of f that are not fixed. Now f ( m + 1) = m or f ( m + 1) = m + 1. For m < k < n ,given the selection of f (1) , f (2) , . . . , f ( k − 1), k − 1 of the k + 1 possible values of f ( k + 1) (1 , 2 , 3 , . . . , k , and counting m twice) have been taken, so there are two distinct values that f ( k + 1) can take (one of them is k + 1, and the other is not, so they are distinct). For f ( n ), when the other 2010 values of f have been assigned, there is only one missing, so f ( n ) is determined. n − m − 1 For each integer in [ m, n ), there are two possible values of f , so there are 2 different functions f for a given m, n . So our answer is 2010 2011 2010 2011 ∑ ∑ ∑ ∑ n − m − 1 − m − 1 n 2 = 2 2 m =1 n = m +1 m =1 n = m +1 2010 ∑ − m − 1 2012 m +1 = 2 (2 − 2 ) m =1 2010 ∑ 2011 − m = 2 − 1 m =1 ( ) 2010 ∑ m = 2 − 2010 m =1 2011 = 2 − 2012 2 π 2 π