HMMT 二月 2012 · TEAM2 赛 · 第 7 题

HMMT February 2012 — TEAM2 Round — Problem 7

[ 20 ] (a) For what positive integers n do there exist functions f, g : { 1 , 2 , . . . , n } → { 1 , 2 , . . . , n } such that for all 1 ≤ i ≤ n , we have that exactly one of f ( g ( i )) = i and g ( f ( i )) = i holds? (b) What if f, g must be permutations?

解析

[ 20 ] For what positive integers n do there exist functions f, g : { 1 , 2 , . . . , n } → { 1 , 2 , . . . , n } such that for each 1 ≤ i ≤ n , either f ( g ( i )) = i or g ( f ( i )) = i , but not both? Answer: n even We claim that this is possible for all even n . First, a construction: set f (2 m − 1) = n f (2 m ) = 2 m − 1 and g (2 m − 1) = g (2 m ) = 2 m for m = 1 , . . . , . It is easy to verify that this solution 2 works. Now, we show that this is impossible for odd n . Without loss of generality, suppose that f ( g (1)) = 1 and that g (1) = a ⇒ f ( a ) = 1. Then, we have g ( f ( a )) = g ( a ) = 1. Consequently, a 6 = 1. In this case, call 1 and a a pair (we likewise regard i and j as a pair when g ( f ( i )) = i and f ( i ) = j ). Now, to show that n is even it suffices to show that all pairs are disjoint. Suppose for the sake of contradiction that some integer b 6 = a is also in a pair with 1 (note that 1 is arbitrary). Then, we have f ( g ( b )) = b, g ( b ) = 1 or g ( f ( b )) = b, f ( b ) = 1. But we already know that g (1) = a , so we must have f ( g ( b )) = b, g ( b ) = 1. But that would mean that both f ( g (1)) = 1 and g ( f (1)) = 1, a contradiction.