Maths Olympiad Prep

Library / NMO Selection Tests /11 of 23

NMO Selection Tests

Combinatorics Difficulty 8.4 Shortlist Prove it Romania

Let n≥3n \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=∑k∈Aaks_A = \sum_{k \in A} a_k, then arranges these sums in increasing order, obtaining the sequence s1≤s2≤⋯≤s2n−1s_1 \le s_2 \le \dots \le s_{2^{n}-1}.
Show that there exists a subset B⊂{1,2,…,2n−1}B \subset \{1, 2, \dots, 2^n - 1\}, with 2n−2+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 i∈Bi \in B.
Cristi Săvescu

Solution

Assume a1≤a2≤⋯≤ana_1 \le a_2 \le \dots \le a_n. If we choose the subset B′={1,2,…,2n−2}B' = \{1, 2, \dots, 2^{n-2}\}, then among the sums s1,s2,…,s2n−2s_1, s_2, \dots, s_{2^{n-2}}, the values a1,a2,…,ata_1, a_2, \dots, a_t will appear for some t≥1t \ge 1. Clearly, s1=s{1}=a1s_1 = s_{\{1\}} = a_1, and if aia_i appears as a sum, then ai−1a_{i-1} must have appeared before it.
Indeed, consider:

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

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

If t≤n−2t \le n-2, then at most 2n−2−12^{n-2}-1 sums can appear, corresponding to non-empty subsets of {1,2,…,n−2}\{1, 2, \dots, n-2\}. Hence, we deduce that t≥n−1t \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,…,an−1a_1, a_2, \dots, a_{n-1}.
If we also include the index 2n−12^n - 1, we obtain s2n−1s_{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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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