HMMT 二月 2011 · TEAM1 赛 · 第 15 题
HMMT February 2011 — TEAM1 Round — Problem 15
题目详情
- [ 55 ] Denote { 1 , 2 , ..., n } by [ n ], and let S be the set of all permutations of [ n ]. Call a subset T of S good if every permutation σ in S may be written as t t for elements t and t of T , where the product 1 2 1 2 of two permutations is defined to be their composition. Call a subset of U of S extremely good if every − 1 permutation σ in S may be written as s us for elements s of S and u of U . Let τ be the smallest value of | T | / | S | for all good subsets T , and let υ be the smallest value of | U | / | S | for all extremely good √ subsets U . Prove that υ ≥ τ . Page 3 of 3
解析
- [ 55 ] Denote { 1 , 2 , ..., n } by [ n ], and let S be the set of all permutations of [ n ]. Call a subset T of S good if every permutation σ in S may be written as t t for elements t and t of T , where the product 1 2 1 2 of two permutations is defined to be their composition. Call a subset of U of S extremely good if every − 1 permutation σ in S may be written as s us for elements s of S and u of U . Let τ be the smallest value of | T | / | S | for all good subsets T , and let υ be the smallest value of | U | / | S | for all extremely good √ subsets U . Prove that υ ≥ τ . Solution: Denote { 1 , 2 , ..., n } by [ n ], and let S be the set of all permutations of [ n ]. Call a subset T of S good if every permutation σ in S may be written as t t for elements t and t of T , where 1 2 1 2 the product of two permutations is defined to be their composition. Call a subset of U of S extremely − 1 good if every permutation σ in S may be written as s us for elements s of S and u of U . Let τ be Team Round A the smallest value of | T | / | S | for all good subsets T , and let υ be the smallest value of | U | / | S | for all √ extremely good subsets U . Prove that υ ≥ τ . 2 Call an element t ∈ S an involution if and only if t is the identity permutation. We claim that the set of all involutions in S constitutes a good subset of S . The proof is simple. Let s be an arbitrary permutation in S . Note that s may be decomposed into a product of disjoint cycles of length at least 2, and suppose that there are m such cycles in its decomposition. For 1 ≤ i ≤ m , let l denote the i length of the i th cycle, so that s may be written as ( a a . . . a )( a a . . . a ) . . . ( a a . . . a ) 1 , 1 1 , 2 1 ,l 2 , 1 2 , 2 2 ,l m, 1 m, 2 m,l 1 2 m for some pairwise distinct elements a , a , . . . , a , a , a , . . . , a , . . . , a , a , . . . , a 1 , 1 1 , 2 1 ,l 2 , 1 2 , 2 2 ,l m, 1 m, 2 m,l 1 2 m of [ n ]. Consider the permutations q and r defined by q ( a ) = a for all 1 ≤ j ≤ l and i,j i,l +1 − j i i r ( a ) = a and r ( a ) = a for all 2 ≤ k ≤ l , for all 1 ≤ i ≤ m , and by q ( x ) = r ( x ) = x for i, 1 i, 1 i,k i,l +2 − k i i 2 2 all x ∈ [ n ] otherwise. Since q, r ∈ S , q = r = 1, and rq = s , it follows that the set of all involutions in S is indeed good, as desired. λ For all integer partitions λ of n , let f denote the number of standard Young tableaux of shape λ . By the Robinson-Schensted-Knuth correspondence, the permutations of [ n ] are in bijection with pairs of standard Young tableaux of the same shape in such a way that the involutions of [ n ] are in bijection with pairs of identical standard Young tableaux. In other words, the number of permutations of [ n ] is equal to the number of pairs of identically shaped standard Young tableaux whose shape is a partition of n , and the number of involutions of [ n ] is equal to the number of standard Young tableaux whose ∑ ∑ λ f λ 2 shape is a partition of n . Hence n ! = ( f ) and τ ≤ , where both sums range over all λ λ n ! partitions λ of n . For all elements u ∈ S , define the conjugacy class of u to be the set of elements that may be written − 1 ′ in the form s us for some s ∈ S . It is easy to see that for all u, u ∈ S , the conjugacy classes of ′ u and u are either identical or disjoint. It follows that S may be partitioned into disjoint conjugacy classes and that any extremely good subset of S must contain at least one element from each distinct conjugacy class. We claim that the number of distinct conjuguacy classes of S is at least the number of integer partitions of n . It turns out that the two numbers are in fact equal, but such a result is not necessary for the purposes of this problem. Let u be an arbitrary permutation in S . Recall that u may be written as ( a a . . . a )( a a . . . a ) . . . ( a a . . . a ) 1 , 1 1 , 2 1 ,l 2 , 1 2 , 2 2 ,l m, 1 m, 2 m,l 1 2 m for some pairwise distinct elements a , a , . . . , a , a , a , . . . , a , . . . , a , a , . . . , a 1 , 1 1 , 2 1 ,l 2 , 1 2 , 2 2 ,l m, 1 m, 2 m,l 1 2 m of [ n ]. Associate to the conjugacy class of u the partition n = l + l + . . . + l + 1 + . . . + 1, where w w w 1 2 m w , w , . . . , w is a partition of 1 , 2 , . . . , m such that w ≥ w ≥ . . . ≥ w and the 1’s represent all the 1 2 m 1 2 m − 1 fixed points of s . Now note that if s is any permutation in S , s us may be written in the form − 1 − 1 − 1 s ( a a . . . a ) ss ( a a . . . a ) s . . . s ( a a . . . a ) s, 1 , 1 1 , 2 1 ,l 2 , 1 2 , 2 2 ,l m, 1 m, 2 m,l 1 2 m which may be written as ( b b . . . b )( b b . . . b ) . . . ( b b . . . b ) 1 , 1 1 , 2 1 ,l 2 , 1 2 , 2 2 ,l m, 1 m, 2 m,l 1 2 m for some pairwise distinct elements b , b , . . . , b , b , b , . . . , b , . . . , b , b , . . . , b 1 , 1 1 , 2 1 ,l 2 , 1 2 , 2 2 ,l m, 1 m, 2 m,l 1 2 m − 1 of [ n ] because multiplying by s on the left and by s on the right is equivalent to re-indexing the letters 1 , 2 , . . . , n . Hence if partitions of n are associated to all conjugacy classes of S analogously, the Team Round A − 1 same partition that is associated to u is associated to s us for all s ∈ S . Since exactly one partition is associated to each conjugacy class, it follows that the number of conjugacy classes cannot exceed the number of partitions, as desired. ∑ 1 To conclude, we need only observe that υ ≥ by our above claim, for then λ n ! √ ( ) ( ) √ √ ∑ ∑ ∑ ∑ √ √ 2 λ √ λ n ! υ = n ! 1 = ( f ) 1 ≥ f ≥ n ! τ λ λ λ λ by the Cauchy-Schwarz inequality, and this completes the proof. Remark: more computationally intensive solutions that do not use Young tableaux but instead calculate the number of involutions explicitly and make use of the generating function for the number of integer partitions are also possible. Team Round A