Maths Olympiad Prep

Library / /11 of 24

Combinatorics Difficulty 8.4 Shortlist Prove it Romania

Let n3n \ge 3 be a natural number. Ana chooses the non-zero natural numbers a1,a2,,ana_1, a_2, \dots, a_n, and for each non-empty subset A{1,2,,n}A \subset \{1, 2, \dots, n\}, she computes the sum sA=kAaks_A = \sum_{k \in A} a_k, then arranges these sums in increasing order, obtaining the sequence s1s2s2n1s_1 \le s_2 \le \dots \le s_{2^{n}-1}.
Show that there exists a subset B{1,2,,2n1}B \subset \{1, 2, \dots, 2^n - 1\}, with 2n2+12^{n-2} + 1 elements, such that, no matter what values Ana chooses for a1,a2,,ana_1, a_2, \dots, a_n, these values can be determined by knowing all the values sis_i, for iBi \in B.
Cristi Săvescu

Solution

Assume a1a2ana_1 \le a_2 \le \dots \le a_n. If we choose the subset B={1,2,,2n2}B' = \{1, 2, \dots, 2^{n-2}\}, then among the sums s1,s2,,s2n2s_1, s_2, \dots, s_{2^{n-2}}, the values a1,a2,,ata_1, a_2, \dots, a_t will appear for some t1t \ge 1. Clearly, s1=s{1}=a1s_1 = s_{\{1\}} = a_1, and if aia_i appears as a sum, then ai1a_{i-1} must have appeared before it.
Indeed, consider:

a) if ai1=aia_{i-1} = a_i, then the appearance is obvious.

b) if ai1<aia_{i-1} < a_i, then since s{i1}=ai1<ais_{\{i-1\}} = a_{i-1} < a_i and aia_i appears as some sjs_j, the index corresponding to ai1a_{i-1} is less than jj, hence ai1a_{i-1} appeared earlier.

If tn2t \le n-2, then at most 2n212^{n-2}-1 sums can appear, corresponding to non-empty subsets of {1,2,,n2}\{1, 2, \dots, n-2\}. Hence, we deduce that tn1t \ge n-1.
Therefore, the first two sums correspond to the numbers a1a_1 and a2a_2. Then, inductively, after determining the numbers a1,a2,,aka_1, a_2, \dots, a_k, we compute all the subset sums of {a1,a2,,ak}\{a_1, a_2, \dots, a_k\}, remove them from the list of known sums, and the smallest remaining sum must be ak+1a_{k+1}.
So, we can determine the numbers a1,a2,,an1a_1, a_2, \dots, a_{n-1}.
If we also include the index 2n12^n - 1, we obtain s2n1s_{2^n-1}, which is the total sum of all numbers. Then we can compute ana_n, and thus all numbers.

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.