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

英文解析

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
    ∑ ∑
    min( a , b )?
    i ji =1 j =1
    Answer: 5530 Let x , for 1 ≤ k ≤ 40, be the number of integers i with 1 ≤ i ≤ 20 such thatka ≥ k . Let y , for 1 ≤ k ≤ 40, be the number of integers j with 1 ≤ j ≤ 20 such that b ≥ k . Iti k jfollows from the problem statement that x + y is the number of elements of the set { 1 , . . . , 40 } whichk kare 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 . Soi j i jfor a fixed k with 1 ≤ k ≤ 40, the number of pairs ( i, j ) with 1 ≤ i, j ≤ 20 such that min( a , b ) ≥ k isi jequal to x y . So we can rewritek k
    20 20 40
    ∑ ∑ ∑
    min( a , b ) = x y .
    i j k ki =1 j =1
    k =1
    Since x + y = 41 − k for 1 ≤ k ≤ 40, we havek k
    ⌊ ⌋ ⌈ ⌉
    41 − k 41 − kx y ≤
    k k
    2 2
    by a convexity argument. So
    ⌊ ⌋ ⌈ ⌉
    20 20 40
    ∑ ∑ ∑
    41 − k 41 − kmin( 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