HMMT 十一月 2023 · 团队赛 · 第 8 题

HMMT November 2023 — Team Round — Problem 8

[55] There are n ≥ 2 coins, each with a different positive integer value. Call an integer m sticky if some subset of these n coins have total value m . We call the entire set of coins a stick if all the sticky numbers form a consecutive range of integers. Compute the minimum total value of a stick across all sticks containing a coin of value 100 . ( ) 127

解析

[55] There are n ≥ 2 coins, each with a different positive integer value. Call an integer m sticky if some subset of these n coins have total value m . We call the entire set of coins a stick if all the sticky numbers form a consecutive range of integers. Compute the minimum total value of a stick across all sticks containing a coin of value 100. Proposed by: Albert Wang Answer: 199 Solution: Sort a stick by increasing value. Note that all sticks must contain 1 by necessity, or the largest and second largest sticky values would not be consecutive. So, let’s say a stick’s highest coin value is a , and all the other terms have a value of S . If a ≥ S +2, we cannot build S +1, but we can pro- duce S and S +2, meaning that this cannot happen. So, a ≤ S +1, and therefore 100 ≤ S +1 → S ≥ 99 giving a lower bound on the answer of 199 . This is easily achievable by picking any stick with S = 99. For instance, { 1 , 2 , 3 , 7 , 12 , 24 , 50 , 100 } is a construction. 127