There is a set of coins with distinct integer weights . It is known that if any coin with weight , , is removed from the set, the remaining coins can be split into two groups of the same weight. (The number of coins in the two groups can be different.) Find all for which such a set of coins exists.
(This problem was suggested by Gregory Galperin.)
Solution
The only such are and odd at least . We divide into cases: even, , , , and odd.
Case 1: even. Suppose for contradiction that such a set exists, and choose one with minimal total weight. Let be the sum of the weights, and note that
Hence
Since is even, it follows that is even, and so also that is even for all . But then the set is another set of weights with the desired property, contradicting minimality. Hence odd fails.
Case 2: . Trivially yes.
Case 3: . Removing any weight leaves two unequal weights.
Case 4: . Suppose for contradiction that such a set exists: order the weights such that . Let . For each , the only possible ways to split the weights other than are as or (in all other combinations, the side with is strictly heavier than the other). By pigeonhole, one of the equations is satisfied for two values of , and the corresponding weights are equal, contradiction.
Case 5: odd. Checking the cases , , and is straightforward casework: the sets suffice. For example, if , the set is and
Suppose there exists such a set for and , let and be the corresponding set of weights and let . Consider the set of weights . These are distinct (each is less than the next in the list by assumption). If weight is removed, then by the inductive hypothesis the other 's can be sorted into two groups of equal weight, as can the 's other than , so the remaining weights can be divided into two groups of equal weight. If weight is removed, then put all the weights together to get weights . By the inductive hypothesis these can be divided into two groups of equal weight. Hence if such a set exists for and , it exists for .
Taking , we see that if a set exists for , one also exists for . By induction, it follows that a set exists for all of the form , , and , where is a non-negative integer. Since this covers all odd numbers greater than , we are done.