HMMT 二月 2011 · ALGCOMB 赛 · 第 16 题

英文解析

16. Let A = { 1 , 2 , . . . , 2011 } . Find the number of functions f from A to A that satisfy f ( n ) ≤ n for all nin 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 Athat 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. Itfollows from backwards induction that for x > n , f ( x ) = x . Therefore n > m , and there are only n − mvalues 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, sothere are two distinct values that f ( k + 1) can take (one of them is k + 1, and the other is not, so theyare 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 functionsf 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
    ∑
    = 2 − 2010 mm =1
    2011 = 2 − 2012
    2 π 2 π