PUMaC 2020 · 代数（A 组） · 第 8 题
PUMaC 2020 — Algebra (Division A) — Problem 8
题目详情
- Let a be the number of unordered sets of three distinct bijections f, g, h : { 1 , 2 , ..., n } → n { 1 , 2 , ..., n } such that the composition of any two of the bijections equals the third. What is the largest value in the sequence a , a , ... which is less than 2021? 1 2 1
解析
- Let a be the number of unordered sets of three distinct bijections f, g, h : { 1 , 2 , ..., n } → n { 1 , 2 , ..., n } such that the composition of any two of the bijections equals the third. What is the largest value in the sequence a , a , ... which is less than 2021? 1 2 Proposed by: Austen Mazenko Answer: 875 First, h := f ◦ g = g ◦ f , so f ( h ( x )) = f ( g ( f ( x ))) = g ( x ). Since g is bijective, this holds iff 2 2 2 g ( f ( g ( f ( x )))) = h ( h ( x )) = g ( g ( x ))), so by analogous equations we find f = g = h . But, 3 2 we also have h ( f ( x )) = g ( x ) = ⇒ g ( f ( f ( x ))) = g ( x ) = g ( x ) = ⇒ g ( x ) ≡ x ; analogous reasoning holds for the other two functions, so they must be involutions. Suppose f ’s cycles are ( a , b ) , ( a , b ) , ..., ( a , b ) (meaning f ( a ) = b , f ( b ) = a )) while 1 1 2 2 n n 1 1 1 1 every other value is a fixed point of f . We will consider the number of possibilities for g (each of which fixes h ). To start, note f ( g ( a )) = g ( f ( a )) = ⇒ f ( g ( a )) = g ( b ). If g ( a ) = a , 1 1 1 1 1 1 then g ( b ) = b so a , b are fixed points of g and ( a , b ) is a cycle in h . If g ( a ) = b , then 1 1 1 1 1 1 1 1 ( a , b ) is a cycle in g , and a , b are fixed points in h . If g ( a ) = a or b for some i > 1, 1 1 1 1 1 i i then g ( b ) = b , so g has cycles ( a , a ) , ( b , b ). Furthermore, f ( g ( a )) = b , ( a , b ) , ( a , b ) 1 i 1 i 1 i 1 i 1 i i 1 are cycles in h . Finally, g ( a ) cannot be a fixed point of f since then f ( g ( a )) = g ( a ) = g ( b ), 1 1 1 1 contradicting bijectivity. Analogous reasoning holds for the other cycles of f . The other possibility is to let x be a fixed point of f , and consider f ( g ( x )) = g ( f ( x )) = g ( x ); 1 1 1 1 hence, g ( x ) is also a fixed point of f . Either g ( x ) = x , meaning g ( x ) = x and h ( x ) = x , 1 1 1 1 1 1 1 or g ( x ) = x for some x , implying h ( x ) = x . 1 2 2 1 2 Combining the above information is sufficient to form a recursion for a . Evidently, a = a = n 0 1 a = a = 0. Now, for n ≥ 4 there are a few possibilities. First, n could be a fixed point of 2 3 f, g, and h , giving a possibilities. Second, n could be paired with some other value m such n − 1 that ( m, n ) is a cycle in two of f, g, h and fixed by the third. There are n − 1 ways to select m , 3 ways to determine which of f, g, h will fix m and n , and then a triplets to pick from. n − 2 However, this situation is also possible when two of f, g, h are identical on { 1 , 2 , ..., n − 1 }{ m } , and the third is the identity function on this set. WLOG f ≡ g and h is the identity: if f fixes m, n while g does not, this will make f, g, h different on { 1 , 2 , ..., n } . The number of ways 4 for f ≡ g is simply the number of involutions on n − 2 elements, minus 1 for the case when f, g, h are all the identity bijection. Let b denote the number of involutions on n elements. n Evidently b = 1 , b = 1 , and for n ≥ 2 either n is fixed or it’s transposed with one of the other 0 1 n − 1 terms, so b = b + ( n − 1) b . Hence, starting with index 0, the sequence { b } is n n − 1 n − 2 n 1 , 1 , 2 , 4 , 10 , 26 , 76 , ... . Thus, this situation adds ( n − 1)( b − 1) to our count. n − 2 The third and final possibility is that n is part of a cycle which is ”paired” with another cycle. This corresponds to the previously outlined scenario when ( a , b ) , ( a , b ) are cycles of f and 1 1 i i ( a , a ) or ( a , b ) is a cycle of g , in which case ( a , b ) or ( a , a ), respectively, is a cycle of h . 1 i 1 i 1 i 1 i ( ) n − 1 If n is in such a pairing, there are ways to select the other three values. Then, if f, g, h 3 are distinct when restricted to the set excluding these four values, there are 3! ways to assign ( ) n − 1 the cycles, contributing 6 a cases. As before, if exactly two of f, g, h are the same, we n − 4 3 ( ) n − 1 will have 3 ways to assign the cycles, so this case contributes 3 · ( b − 1) to our tally. n − 4 3 Finally, if f, g, h are each the identity on the restriction to all but the four values of interest, ( ) n − 1 we get an additional possibilities. 3 Hence, ( ) ( ) ( ) n − 1 n − 1 n − 1 a = a +3( n − 1) · a +( n − 1) · ( b − 1)+6 · · a +3 · · ( b − 1)+ . n n − 1 n − 2 n − 2 n − 4 n − 4 3 3 3 Simply plugging into the recurrence gives a = 4 , a = 20 , a = 165 , and a = 875. It is 4 5 6 7 evident a is too large and the sequence is monotonically increasing, so our answer is 875 . 8 5