Maths Olympiad Prep

Library / /10 of 18

Combinatorics Difficulty 6.2 National olympiad Prove it Belarus

Find all positive integers nn (n<24n < 24) such that the set M={n,n+1,,24}M = \{n, n + 1, \dots, 24\} can be partitioned into some disjoint subsets so that in each subset one of the numbers is equal to the sum of all other numbers of this subset.
(V. Kaskevich)

Solution

A number aa from a subset of the desired partition is called major if aa is equal to the sum of all other numbers of this subset. All numbers in each subset must be distinct, since one of them is major we see that there exist at least three numbers in each subset. Let kk be the number of the subsets of the desired partition. Since we have 25n25-n numbers in the initial set M={n,n+1,,24}M = \{n, n+1, \dots, 24\}, we have k25n3k \le \frac{25-n}{3}. On the other hand, if aa is the major number of some subset, then the sum of the numbers of this subset is equal to 2a2a. So the sum S(n)S(n) of all numbers of the set MM must be even than or equal to
2(24+23+22++(25k))=2(24+25k)k2=(49k)k(4925n3)25n3=(122+n)(25n)9. 2 \cdot (24 + 23 + 22 + \dots + (25 - k)) = 2 \cdot \frac{(24 + 25 - k) \cdot k}{2} = (49 - k) \cdot k \le \\ \le \left(49 - \frac{25-n}{3}\right) \cdot \frac{25-n}{3} = \frac{(122+n)(25-n)}{9}.
(The last inequality holds because k25n/349/2k \le 25-n/3 \le 49/2, and the function (49x)x(49-x)x increases for x49/2x \le 49/2.) Therefore, the following condition is necessary to exist the desired partition:
S(n)(122+n)(25n)9    (n+24)(25n)2(122+n)(25n)9    9(n+24)2(122+n)    n4. S(n) \le \frac{(122+n)(25-n)}{9} \iff \frac{(n+24)(25-n)}{2} \le \frac{(122+n)(25-n)}{9} \iff 9(n+24) \le 2(122+n) \iff n \le 4.
For n=2n=2 and n=3n=3 we see that both the sums
S(2)=(2+24)(252)2=1323,S(3)=(3+24)(253)2=2711 S(2) = \frac{(2+24)(25-2)}{2} = 13 \cdot 23, \quad S(3) = \frac{(3+24)(25-3)}{2} = 27 \cdot 11
are odd, so the desired partitions do not exist.

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 and solution reproduced as published; topic and difficulty added by this site.