HMMT 二月 2016 · COMB 赛 · 第 10 题

英文解析

10. Kristoff is planning to transport a number of indivisible ice blocks with positive integer weights from the north mountain to Arendelle. He knows that when he reaches Arendelle, Princess Anna and Queen
    Elsa will name an ordered pair ( p, q ) of nonnegative integers satisfying p + q ≤ 2016. Kristoff must thengive Princess Anna exactly p kilograms of ice. Afterward, he must give Queen Elsa exactly q kilogramsof ice.
    What is the minimum number of blocks of ice Kristoff must carry to guarantee that he can alwaysmeet Anna and Elsa’s demands, regardless of which p and q are chosen?
    Proposed by: Pakawut Jiradilok
    Answer: 18
    The answer is 18.
    First, we will show that Kristoff must carry at least 18 ice blocks. Let
    0 < x ≤ x ≤ · · · ≤ x
    1 2 nbe the weights of ice blocks he carries which satisfy the condition that for any p, q ∈ Z such that
    ≥ 0
    ∑ ∑
    p + q ≤ 2016, there are disjoint subsets I, J of { 1 , . . . , n } such that x = p and x = q .
    α αα ∈ I α ∈ J
    Claim : For any i , if x + · · · + x ≤ 2014, then
    1 i
    ⌊ ⌋
    x + · · · + x
    1 ix ≤ + 1 .
    i +1
    x + ··· + x 2
    1 i
    Proof. Suppose to the contrary that x ≥ b c +2. Consider when Anna and Elsa both demandi +1
    2 ( )
    x + ··· + x x + ··· + x
    1 i 1 ib c + 1 kilograms of ice (which is possible as 2 × b c + 1 ≤ x + · · · + x + 2 ≤ 2016).
    1 i
    2 2
    Kristoff cannot give any ice x with j ≥ i + 1 (which is too heavy), so he has to use from x , . . . , x .
    j 1 i
    ( )
    x + ··· + x
    1 i
    Since he is always able to satisfy Anna’s and Elsa’s demands, x + · · · + x ≥ 2 × b c + 1 ≥
    1 ix + · · · + x + 1. A contradiction.2
    1 i
    It is easy to see x = 1, so by hand we compute obtain the inequalities x ≤ 1, x ≤ 2, x ≤ 3, x ≤ 4,
    1 2 3 4 5
    x ≤ 6, x ≤ 9, x ≤ 14, x ≤ 21, x ≤ 31, x ≤ 47, x ≤ 70, x ≤ 105, x ≤ 158, x ≤ 237,
    6 7 8 9 10 11 12 13 14 15
    x ≤ 355, x ≤ 533, x ≤ 799. And we know n ≥ 18; otherwise the sum x + · · · + x would not
    16 17 18 1 nreach 2016.
    Now we will prove that n = 18 works. Consider the 18 numbers named above, say a = 1, a = 1,
    1 2
    a = 2, a = 3, . . . , a = 799. We claim that with a , . . . , a , for any p, q ∈ Z such that
    3 4 18 1 k ≥ 0
    ∑
    p + q ≤ a + · · · + a , there are two disjoint subsets I, J of { 1 , . . . , k } such that x = p and
    1 k αα ∈ I
    ∑
    x = q . We prove this by induction on k . It is clear for small k = 1 , 2 , 3. Now suppose this isαα ∈ Jtrue for a certain k , and we add in a . When Kristoff meets Anna first and she demands p kilogramsk +1
    of ice, there are two cases.
    ′
    Case I: if p ≥ a , then Kristoff gives the a block to Anna first, then he consider p = p − ak +1 k +1 k +1
    ′
    and the same unknown q . Now p + q ≤ a + · · · + a and he has a , . . . , a , so by induction he can
    1 k 1 ksuccessfully complete his task.
    Case II: if p < a , regardless of the value of q , he uses the same strategy as if p + q ≤ a + · · · + a andk +1 1 khe uses ice from a , . . . , a without touching a . Then, when he meets Elsa, if q ≤ a + · · · + a − p ,
    1 k k +1 1 k
    ( )
    a + ··· + a
    1 khe is safe. If q ≥ a + · · · + a − p + 1, we know q − a ≥ a + · · · + a − p + 1 − b c + 1 ≥ 0.
    1 k k +1 1 k
    ′2
    So he can give the a to Elsa first then do as if q = q − a is the new demand by Elsa. He cank +1 k +1
    ′
    now supply the ice to Elsa because p + q ≤ a + · · · + a . Thus, we finish our induction.
    1 k
    Therefore, Kristoff can carry those 18 blocks of ice and be certain that for any p + q ≤ a + · · · + a =
    1 18
    ∑ ∑
    2396, there are two disjoint subsets I, J ⊆ { 1 , . . . , 18 } such that a = p and a = q . Inα αα ∈ I α ∈ Jother words, he can deliver the amount of ice both Anna and Elsa demand.