HMMT 十一月 2016 · 冲刺赛 · 第 21 题

英文解析

21. [ 11 ] Zlatan has 2017 socks of various colours. He wants to proudly display one sock of each of thecolours, and he counts that there are N ways to select socks from his collection for display. Given thisinformation, what is the maximum value of N ?
    Proposed by: Saranesh Prembabu
    Answer: 3 · 4671
    Say that there are k sock types labeled 1 , 2 , . . . , k , and a socks of type i . The problem asks to maximizei
    ∏ ∑
    k ka subject to a = 2017, over all k and all sequences of positive integers a , . . . , a .
    i i 1 ki =1 i =1
    The optimal ( a , . . . , a ) cannot have any a = 1 for any i , because if there exists a = 1 we can delete
    1 k i ithis a and add 1 to any a ( j 6 = i ) to increase the product while keeping the sum constant.
    i j
    There exists an optimal ( a , . . . , a ) without any a ≥ 4 because if there exists a ≥ 4 we can replace
    1 k i ithis a with a − 2 and 2, which nonstrictly increases the product while keeping the sum constant.
    i i
    Therefore, there exists an optimal ( a , . . . , a ) whose terms are all 2 or 3. The optimal ( a , . . . , a )
    1 k 1 kcannot have more than two 2 s, because we can replace three 2 s with two 3 s, which increases the sum
    3 92
    by a factor of = while keeping the sum constant.
    2 83
    It follows that we want to partition 2017 into 671 3 s and two 2 s, for a product of 3 · 4.671