Maths Olympiad Prep

Library / /38 of 45

Combinatorics Difficulty 9.0 Shortlist Prove it United States

There is a set of nn coins with distinct integer weights w1,w2,,wnw_1, w_2, \dots, w_n. It is known that if any coin with weight wkw_k, 1kn1 \le k \le n, 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 nn for which such a set of coins exists.
(This problem was suggested by Gregory Galperin.)

Solution

The only such nn are 11 and odd nn at least 77. We divide into cases: nn even, n=1n = 1, n=3n = 3, n=5n = 5, and n7n \ge 7 odd.

Case 1: nn even. Suppose for contradiction that such a set exists, and choose one with minimal total weight. Let ss be the sum of the weights, and note that
sw1swn0(mod2). s - w_1 \equiv \dots \equiv s - w_n \equiv 0 \pmod{2}.
Hence
w1wn(mod2). w_1 \equiv \dots \equiv w_n \pmod{2}.
Since nn is even, it follows that ss is even, and so also that wiw_i is even for all ii. But then the set {wi/2}\{w_i/2\} is another set of nn weights with the desired property, contradicting minimality. Hence nn odd fails.

Case 2: n=1n = 1. Trivially yes.

Case 3: n=3n = 3. Removing any weight leaves two unequal weights.

Case 4: n=5n = 5. Suppose for contradiction that such a set exists: order the weights such that w1<w2<w3<w4<w5w_1 < w_2 < w_3 < w_4 < w_5. Let t=w2+w3+w4t = w_2 + w_3 + w_4. For each i{2,3,4}i \in \{2, 3, 4\}, the only possible ways to split the weights other than wiw_i are as w5=twi+w1w_5 = t - w_i + w_1 or w5+w1=twiw_5 + w_1 = t - w_i (in all other combinations, the side with w5w_5 is strictly heavier than the other). By pigeonhole, one of the equations is satisfied for two values of ii, and the corresponding weights are equal, contradiction.

Case 5: n7n \ge 7 odd. Checking the cases n=7n = 7, n=9n = 9, and n=11n = 11 is straightforward casework: the sets {1,3,5,,2n1}\{1, 3, 5, \dots, 2n - 1\} suffice. For example, if n=7n = 7, the set is {1,3,5,,13}\{1, 3, 5, \dots, 13\} and
3+5+7+9=11+131+9+13=5+7+111+3+7+11=9+131+9+11=3+5+131+3+5+11=7+131+5+13=3+7+91+3+5+9=7+11. \begin{aligned} 3 + 5 + 7 + 9 &= 11 + 13 \\ 1 + 9 + 13 &= 5 + 7 + 11 \\ 1 + 3 + 7 + 11 &= 9 + 13 \\ 1 + 9 + 11 &= 3 + 5 + 13 \\ 1 + 3 + 5 + 11 &= 7 + 13 \\ 1 + 5 + 13 &= 3 + 7 + 9 \\ 1 + 3 + 5 + 9 &= 7 + 11. \end{aligned}
Suppose there exists such a set for n=kn = k and n=jn = j, let w1<w2<<wkw_1 < w_2 < \dots < w_k and v1<<vjv_1 < \dots < v_j be the corresponding set of weights and let s=v1++vjs = v_1 + \dots + v_j. Consider the set of weights w1v1,w1v2,,w1vj,w2s,w3s,,wksw_1v_1, w_1v_2, \dots, w_1v_j, w_2s, w_3s, \dots, w_ks. These are distinct (each is less than the next in the list by assumption). If weight w1viw_1v_i is removed, then by the inductive hypothesis the other vv's can be sorted into two groups of equal weight, as can the ww's other than w1w_1, so the remaining weights can be divided into two groups of equal weight. If weight wisw_is is removed, then put all the weights w1v1,,w1vjw_1v_1, \dots, w_1v_j together to get weights w1s,w2s,,wi1s,wi+1s,,wksw_1s, w_2s, \dots, w_{i-1}s, w_{i+1}s, \dots, w_ks. By the inductive hypothesis these can be divided into two groups of equal weight. Hence if such a set exists for n=kn = k and n=jn = j, it exists for k+j1k + j - 1.

Taking j=7j = 7, we see that if a set exists for n=kn = k, one also exists for n=k+6n = k + 6. By induction, it follows that a set exists for all nn of the form 6m+76m + 7, 6m+96m + 9, and 6m+116m + 11, where mm is a non-negative integer. Since this covers all odd numbers greater than 77, we are done.

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.