HMMT 二月 2024 · COMB 赛 · 第 9 题
HMMT February 2024 — COMB Round — Problem 9
题目详情
- Compute the number of triples ( f, g, h ) of permutations on { 1 , 2 , 3 , 4 , 5 } such that f ( g ( h ( x ))) = h ( g ( f ( x ))) = g ( x ) , g ( h ( f ( x ))) = f ( h ( g ( x ))) = h ( x ) , and h ( f ( g ( x ))) = g ( f ( h ( x ))) = f ( x ) for all x ∈ { 1 , 2 , 3 , 4 , 5 } .
解析
- Compute the number of triples ( f, g, h ) of permutations on { 1 , 2 , 3 , 4 , 5 } such that f ( g ( h ( x ))) = h ( g ( f ( x ))) = g ( x ) , g ( h ( f ( x ))) = f ( h ( g ( x ))) = h ( x ) , and h ( f ( g ( x ))) = g ( f ( h ( x ))) = f ( x ) for all x ∈ { 1 , 2 , 3 , 4 , 5 } . Proposed by: Rishabh Das Answer: 146 Solution: Let f g represent the composition of permutations f and g , where ( f g )( x ) = f ( g ( x )) for all x ∈ { 1 , 2 , 3 , 4 , 5 } . Evaluating f ghf h in two ways, we get f = gf h = ( f gh ) f h = f ghf h = f ( ghf ) h = f hh, so hh = 1 . Similarly, we get f , g , and h are all involutions. Then f gh = g = ⇒ f g = gh, so f g = gh = hf . Let x := f g = gh = hf . Then 3 x = ( f g )( gh )( hf ) = 1 . We can also show that f g = gh = hf along with f, g, h being involutions is enough to recover the initial conditions, so we focus on satisfying these new conditions. ( ) ( ) 5 5 1 If x = 1 , then f = g = h is an involution. There are 1 + + = 26 involutions, so this case 2 2 2 , 2 , 1 gives 26 solutions. 3 Suppose x ̸ = 1 . Then since x = 1 , x is composed of a 3 -cycle and two fixed points, of which there are 20 choices. WLOG x = (1 2 3) . It can be checked that { 1 , 2 , 3 } must map to itself for all of f, g, h and also { 4 , 5 } . We can either have all of f, g, h map 4 and 5 to themselves or each other. Restricted to { 1 , 2 , 3 } , they are some rotation of (1 2) , (2 3) , (1 3) . Each of the 20 cases thus gives 2 · 3 = 6 triples, so overall we get 20 · 6 = 120 . The final answer is 26 + 120 = 146 .