HMMT 二月 2012 · 冲刺赛 · 第 27 题
HMMT February 2012 — Guts Round — Problem 27
题目详情
- [ 17 ] Let S be the set { 1 , 2 , . . . , 2012 } . A perfectutation is a bijective function h from S to itself such that there exists an a ∈ S such that h ( a ) 6 = a , and that for any pair of integers a ∈ S and b ∈ S such k that h ( a ) 6 = a , h ( b ) 6 = b , there exists a positive integer k such that h ( a ) = b . Let n be the number of ordered 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.
解析
- [ 17 ] Let S be the set { 1 , 2 , . . . , 2012 } . A perfectutation is a bijective function h from S to itself such that there exists an a ∈ S such that h ( a ) 6 = a , and that for any pair of integers a ∈ S and b ∈ S such k that h ( a ) 6 = a , h ( b ) 6 = b , there exists a positive integer k such that h ( a ) = b . Let n be the number of ordered 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 cycle that contains more than 1 element. Assume f has k fixed points, and that the other 2012 − k elements form 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 fixed points of f to fixed points of f . It must, therefore send non-fixed points to non-fixed points. This partitions 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 k some m of the fixed points and cycles the rest in ( k − m − 1)! ways. So there are ( k − m − 1)! m =0 m ∑ k − 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 − k f ( 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 − i so g cycles through all the non-fixed points of f , which happens if and only if j − i is relatively prime to 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.