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

HMMT November 2016 — Guts Round — Problem 21

[ 11 ] Zlatan has 2017 socks of various colours. He wants to proudly display one sock of each of the colours, and he counts that there are N ways to select socks from his collection for display. Given this information, what is the maximum value of N ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2016, November 12, 2016 — GUTS ROUND Organization Team Team ID#

解析

[ 11 ] Zlatan has 2017 socks of various colours. He wants to proudly display one sock of each of the colours, and he counts that there are N ways to select socks from his collection for display. Given this information, what is the maximum value of N ? Proposed by: Saranesh Prembabu 671 Answer: 3 · 4 Say that there are k sock types labeled 1 , 2 , . . . , k , and a socks of type i . The problem asks to maximize i ∏ ∑ k k a subject to a = 2017, over all k and all sequences of positive integers a , . . . , a . i i 1 k i =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 i this 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 i this 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 k cannot have more than two 2s, because we can replace three 2s with two 3s, which increases the sum 2 3 9 by a factor of = while keeping the sum constant. 3 2 8 671 It follows that we want to partition 2017 into 671 3s and two 2s, for a product of 3 · 4.