HMMT 二月 2014 · 冲刺赛 · 第 27 题

HMMT February 2014 — Guts Round — Problem 27

[ 17 ] Suppose that ( a , . . . , a ) and ( b , . . . , b ) are two sequences of integers such that the sequence 1 20 1 20 ( a , . . . , a , b , . . . , b ) contains each of the numbers 1 , . . . , 40 exactly once. What is the maximum 1 20 1 20 possible value of the sum 20 20 X X min( a , b )? i j i =1 j =1 n n

解析

[ 17 ] Suppose that ( a , . . . , a ) and ( b , . . . , b ) are two sequences of integers such that the sequence 1 20 1 20 ( a , . . . , a , b , . . . , b ) contains each of the numbers 1 , . . . , 40 exactly once. What is the maximum 1 20 1 20 possible value of the sum 20 20 ∑ ∑ min( a , b )? i j i =1 j =1 Answer: 5530 Let x , for 1 ≤ k ≤ 40, be the number of integers i with 1 ≤ i ≤ 20 such that k a ≥ k . Let y , for 1 ≤ k ≤ 40, be the number of integers j with 1 ≤ j ≤ 20 such that b ≥ k . It i k j follows from the problem statement that x + y is the number of elements of the set { 1 , . . . , 40 } which k k are greater than or equal to 40, which is just 41 − k . Note that if 1 ≤ i, j ≤ 20, and 1 ≤ k ≤ 40, then min( a , b ) ≥ k if and only if a ≥ k and b ≥ k . So i j i j for a fixed k with 1 ≤ k ≤ 40, the number of pairs ( i, j ) with 1 ≤ i, j ≤ 20 such that min( a , b ) ≥ k is i j equal to x y . So we can rewrite k k 20 20 40 ∑ ∑ ∑ min( a , b ) = x y . i j k k i =1 j =1 k =1 Since x + y = 41 − k for 1 ≤ k ≤ 40, we have k k ⌊ ⌋ ⌈ ⌉ 41 − k 41 − k x y ≤ k k 2 2 by a convexity argument. So ⌊ ⌋ ⌈ ⌉ 20 20 40 ∑ ∑ ∑ 41 − k 41 − k min( a , b ) ≤ = 5530 . i j 2 2 i =1 j =1 k =1 Equality holds when ( a , . . . , a ) = (2 , 4 , . . . , 38 , 40) and ( b , . . . , b ) = (1 , 3 , . . . , 37 , 39). 1 20 1 20 n n