HMMT 二月 2012 · 冲刺赛 · 第 27 题
HMMT February 2012 — Guts Round — Problem 27
题目详情
英文原题
[17] Let Sbe the set {1,2, . . . , 2012}. A perfectutation is a bijective function hfrom Sto itself such that there exists an a∈Ssuch that h(a)/ne}ationslash=a, and that for any pair of integers a∈Sandb∈Ssuch thath(a)/ne}ationslash=a,h(b)/ne}ationslash=b, there exists a positive integer ksuch that hk(a) =b. Let nbe the number of ordered pairs of perfectutations ( f, g) such that f(g(i)) =g(f(i)) for all i∈S, but f/ne}ationslash=g. Find the remainder when nis divided by 2011.
解析
英文解析
- [ 17 ] Let S be the set { 1 , 2 , . . . , 2012 } . A perfectutation is a bijective function h from S to itself suchthat there exists an a ∈ S such that h ( a ) 6 = a , and that for any pair of integers a ∈ S and b ∈ S suchthat h ( a ) 6 = a , h ( b ) 6 = b , there exists a positive integer k such that h ( a ) = b . Let n be the number ofkordered pairs of perfectutations ( f, g ) such that f ( g ( i )) = g ( f ( i )) for all i ∈ S , but f 6 = g . Find the remainder when n is divided by 2011.
Answer: 2 Note that both f and g , when written in cycle notation, must contain exactly one cyclethat contains more than 1 element. Assume f has k fixed points, and that the other 2012 − k elementsform a cycle, (of which there are (2011 − k )! ways).
Then note that if f fixes a then f ( g ( a )) = g ( f ( a )) = g ( a ) implies f fixes g ( a ) So g must send fixedpoints of f to fixed points of f . It must, therefore send non-fixed points to non-fixed points. Thispartitions S into two sets, at least one of which must be fixed by g , since g is a perfectutation.
If g fixes all of the the non-fixed points of f , then, since any function commutes with the identity, g fixes
( )
∑
k − 2
some m of the fixed points and cycles the rest in ( k − m − 1)! ways. So there are ( k − m − 1)!km =0
∑mk − 2
k !
choices, which is .
m =0
( k − m ) m !
If g fixes all of the fixed points of f , then order the non-fixed points of f a , a , . . . , a such that
1 2 2012 − kf ( a ) = a . If g ( a ) = a then f ( g ( a )) = a thus g ( a ) = a . Therefore the choice of g ( a )
i i +1 i j i j +1 i +1 j +1 1
uniquely determines g ( a ) for the rest of the i , and g ( a ) = a . But g has to be a perfectutation,
i m m + j − iso g cycles through all the non-fixed points of f , which happens if and only if j − i is relatively primeto 2012 − k . So there are φ (2012 − k ) choices.
∑
k − 2
k !
Therefore for any f there are + φ (2012 − k ) choices of g , but one of them will be g = f ,
m =0 ( k − m ) m !
∑
k − 2
k !
which we cannot have by the problem statement. So there are − 1 + + φ (2012 − k )
m =0
( k − m ) m !
options.
( )
∑
2010
2012
Now note that a permutation can not fix all but one element. So n = (2011 − k )!( − 1 +
k =0 k
∑
k − 2
k !
- φ (2012 − k ))
m =0
( k − m ) m !
Modulo 2011 (which is prime), note that all terms in the summand except the one where k = 1 vanish.
Thus, n ≡ (2010)!( − 1 + ( − 1)) ≡ 2 (mod 2011) by Wilson’s Theorem.