HMMT 二月 2016 · COMB 赛 · 第 10 题
HMMT February 2016 — COMB Round — Problem 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 then give Princess Anna exactly p kilograms of ice. Afterward, he must give Queen Elsa exactly q kilograms of ice. What is the minimum number of blocks of ice Kristoff must carry to guarantee that he can always meet Anna and Elsa’s demands, regardless of which p and q are chosen?
解析
- 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 then give Princess Anna exactly p kilograms of ice. Afterward, he must give Queen Elsa exactly q kilograms of ice. What is the minimum number of blocks of ice Kristoff must carry to guarantee that he can always meet 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 n be 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 i x ≤ + 1 . i +1 2 x + ··· + x 1 i Proof. Suppose to the contrary that x ≥ b c +2. Consider when Anna and Elsa both demand i +1 2 ( ) x + ··· + x x + ··· + x 1 i 1 i b 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 i 2 x + · · · + x + 1. A contradiction. 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 n reach 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 α α ∈ J true for a certain k , and we add in a . When Kristoff meets Anna first and she demands p kilograms k +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 − a k +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 k successfully 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 and k +1 1 k he 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 k he 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 can k +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 α ∈ J other words, he can deliver the amount of ice both Anna and Elsa demand.