HMMT 二月 2011 · TEAM1 赛 · 第 15 题

英文解析

15. [ 55 ] Denote { 1 , 2 , ..., n } by [ n ], and let S be the set of all permutations of [ n ]. Call a subset T of Sgood 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 smallestvalue 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 Athe 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 υ ≥ τ .
    Call an element t ∈ S an involution if and only if t is the identity permutation. We claim that the 2
    set of all involutions in S constitutes a good subset of S . The proof is simple. Let s be an arbitrarypermutation 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 theilength 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 mfor some pairwise distinct elementsa , 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 mof [ n ]. Consider the permutations q and r defined by q ( a ) = a for all 1 ≤ j ≤ l andi,j i,l +1 − j iir ( a ) = a and r ( a ) = a for all 2 ≤ k ≤ l , for all 1 ≤ i ≤ m , and by q ( x ) = r ( x ) = x fori, 1 i, 1 i,k i,l +2 − k i
    2 2 iall x ∈ [ n ] otherwise. Since q, r ∈ S , q = r = 1, and rq = s , it follows that the set of all involutionsin 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 ofstandard Young tableaux of the same shape in such a way that the involutions of [ n ] are in bijectionwith pairs of identical standard Young tableaux. In other words, the number of permutations of [ n ] isequal to the number of pairs of identically shaped standard Young tableaux whose shape is a partitionof 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 conjugacyclasses and that any extremely good subset of S must contain at least one element from each distinctconjugacy class. We claim that the number of distinct conjuguacy classes of S is at least the numberof integer partitions of n . It turns out that the two numbers are in fact equal, but such a result is notnecessary 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 mfor some pairwise distinct elementsa , 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 mof [ n ]. Associate to the conjugacy class of u the partition n = l + l + . . . + l + 1 + . . . + 1, wherew w w
    1 2 mw , 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 mwhich 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 mfor some pairwise distinct elementsb , 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 theletters 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 partitionis associated to each conjugacy class, it follows that the number of conjugacy classes cannot exceedthe number of partitions, as desired.
    ∑
    To conclude, we need only observe that υ ≥ by our above claim, for then 1
    λ 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 calculatethe number of involutions explicitly and make use of the generating function for the number of integerpartitions are also possible.
    Team Round A