Maths Olympiad Prep

Track / Stage 6 / 144 of 400 #1784 of 2604

Problem 1784

National Olympiad, first round
Combinatorics Difficulty 6.2 Prove it Belarus — Final Round · 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)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official 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 25−n25-n numbers in the initial set M={n,n+1,…,24}M = \{n, n+1, \dots, 24\}, we have k≤25−n3k \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+⋯+(25−k))=2⋅(24+25−k)⋅k2=(49−k)⋅k≤≤(49−25−n3)⋅25−n3=(122+n)(25−n)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 k≤25−n/3≤49/2k \le 25-n/3 \le 49/2, and the function (49−x)x(49-x)x increases for x≤49/2x \le 49/2.) Therefore, the following condition is necessary to exist the desired partition:
S(n)≤(122+n)(25−n)9  ⟺  (n+24)(25−n)2≤(122+n)(25−n)9  ⟺  9(n+24)≤2(122+n)  ⟺  n≤4. 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)(25−2)2=13⋅23,S(3)=(3+24)(25−3)2=27⋅11 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.

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