Library / /673 of 740

, 2023

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

There are $n \geq 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$ .

Solution

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 \geq S+2$ , we cannot build $S+1$ , but we can produce $S$ and $S+2$ , meaning that this cannot happen. So, $a \leq S+1$ , and therefore $100 \leq S+1 \rightarrow S \geq 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.