HMMT 十一月 2011 · THM 赛 · 第 5 题

HMMT November 2011 — THM Round — Problem 5

[ 8 ] For any finite sequence of positive integers π , let S ( π ) be the number of strictly increasing sub- sequences in π with length 2 or more. For example, in the sequence π = { 3 , 1 , 2 , 4 } , there are five increasing sub-sequences: { 3 , 4 } , { 1 , 2 } , { 1 , 4 } , { 2 , 4 } , and { 1 , 2 , 4 } , so S ( π ) = 5. In an eight-player game of Fish, Joy is dealt six cards of distinct values, which she puts in a random order π from left to right in her hand. Determine ∑ S ( π ), π where the sum is taken over all possible orders π of the card values. Circles and Tangents

解析

[ 8 ] For any finite sequence of positive integers π , let S ( π ) be the number of strictly increasing sub- sequences in π with length 2 or more. For example, in the sequence π = { 3 , 1 , 2 , 4 } , there are five increasing sub-sequences: { 3 , 4 } , { 1 , 2 } , { 1 , 4 } , { 2 , 4 } , and { 1 , 2 , 4 } , so S ( π ) = 5. In an eight-player game of Fish, Joy is dealt six cards of distinct values, which she puts in a random order π from left to right in her hand. Determine ∑ S ( π ), π where the sum is taken over all possible orders π of the card values. Answer: 8287 For each subset of Joy’s set of cards, we compute the number of orders of cards in which the cards in the subset are arranged in increasing order. When we sum over all subsets of Joy’s cards, we will obtain the desired sum. Consider any subset of k cards. The probability that they are arranged in increasing order is precisely 1 /k ! (since we can form a k !-to-1 correspondence between all possible orders and orders in which the cards in our subset are in increasing order), and there are 6! = 720 total arrangements so exactly 720 /k ! of them give an increasing subsequence in the specified cards. Now for any for k = 2 , 3 , 4 , 5 , 6, ( ) 6 we have subsets of k cards, so we sum to get k ( ) 6 ∑ ∑ 6 6! S ( π ) = · = 8287. k k ! π k =2