HMMT 二月 2011 · 冲刺赛 · 第 31 题
HMMT February 2011 — Guts Round — Problem 31
题目详情
- [ 18 ] Let A = { 1 , 2 , 3 , . . . , 9 } . Find the number of bijective functions f : A → A for which there exists at least one i ∈ A such that − 1 | f ( i ) − f ( i ) | > 1 .
解析
- [ 18 ] Let A = { 1 , 2 , 3 , . . . , 9 } . Find the number of bijective functions f : A → A for which there exists at 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 automatically satisfied for i = j . Otherwise, if f ( f ( j )) = j but f ( j ) = k 6 = j , then we will have f ( f ( k )) = k , allowing the 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 , then f ( f ( k )) = f ( i + 1) = k + 1 or k − 1. Thus the function f allows us to partition the elements of A into three 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 ( ) 9 If a = 2, there are = 36 possibilities. If a = 0, there is 1 possibility. In total, case 1 offers 7 945 + 1260 + 378 + 36 + 1 = 2620 possibilities. 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 described above). For the remaining 5 elements, we divide into cases according to the value of a . If a = 4, there ( ) 5 are 5 × 3 = 15 possibilities. If a = 2, there are = 10 possibilities. If a = 0, there is one possibility. 3 In total, case 2 offers 21 × 2 × (15 + 10 + 1) = 1092 possibilities. Case 3: There are 8 elements of the third type. There are 5 ways to choose the unique element not of the third type. Of the remaining eight, there are 3 ways to divide them into two quartets, and for 2 each quartet, there are 2 ways to assign values of f . In total, case 3 offers 5 × 3 × 2 = 60 possibilities. − 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.