HMMT 二月 2011 · 冲刺赛 · 第 31 题

英文解析

31. [ 18 ] Let A = { 1 , 2 , 3 , . . . , 9 } . Find the number of bijective functions f : A → A for which there existsat least one i ∈ A such that − 1
    | f ( i ) − f ( i ) | > 1 .
    Answer: 359108 − 1
    We count the complement — the number of functions f such that for all i ∈ A , | f ( i ) − f ( i ) | ≤ 1.
    The condition is equivalent to | f ( f ( i )) − i | ≤ 1 for all i ∈ A . If f ( j ) = j , the inequality is automaticallysatisfied for i = j . Otherwise, if f ( f ( j )) = j but f ( j ) = k 6 = j , then we will have f ( f ( k )) = k , allowingthe inequality to be satisfied for i = j, k . Else, if f ( f ( i )) 6 = i , say f ( f ( i )) = i + 1 and f ( i ) = k , thenf ( f ( k )) = f ( i + 1) = k + 1 or k − 1. Thus the function f allows us to partition the elements of A intothree groups:
    (a) those such that f ( i ) = i ,
    (b) those that form pairs { i, j } such that f ( i ) = j and f ( j ) = i , and
    (c) those that form quartets { i, i + 1 , j, j + 1 } such that f permutes them as ( i j i + 1 j + 1) or
    ( i j + 1 i + 1 j ), in cycle notation.
    Let a be the number of elements of the second type. Note that a is even.
    Case 1: There are no elements of the third type. If a = 8, there are 9 · 7 · 5 · 3 = 945 possibilities.
    ( ) ( )
    9 9
    If a = 6, there are · 5 · 3 = 1260 possibilities. If a = 4, there are · 3 = 378 possibilities.
    3 5
    ( )
    If a = 2, there are = 36 possibilities. If a = 0, there is 1 possibility. In total, case 1 offers 9
    945 + 1260 + 378 + 36 + 1 = 2620 possibilities.7
    Case 2: There are 4 elements of the third type. There are 21 ways to choose the quartet { i, i +1 , j, j +1 } .
    For each way, there are two ways to assign the values of the function to each element (as describedabove). For the remaining 5 elements, we divide into cases according to the value of a . If a = 4, there
    ( )
    are 5 × 3 = 15 possibilities. If a = 2, there are = 10 possibilities. If a = 0, there is one possibility.5
    In total, case 2 offers 21 × 2 × (15 + 10 + 1) = 1092 possibilities.3
    Case 3: There are 8 elements of the third type. There are 5 ways to choose the unique element notof the third type. Of the remaining eight, there are 3 ways to divide them into two quartets, and foreach quartet, there are 2 ways to assign values of f . In total, case 3 offers 5 × 3 × 2 = 60 possibilities.2 − 1
    Therefore, the number of functions f : A → A such that for at least one i ∈ A , | f ( i ) − f ( i ) | > 1 is
    9! − 2620 − 1092 − 60 = 359108.