olymmath

ISL 2019 A3

Let n⩾3n \geqslant 3 be a positive integer and let (a1,a2,…,an)\left(a_{1}, a_{2}, \ldots, a_{n}\right) be a strictly increasing sequence of nn positive real numbers with sum equal to 2 . Let XX be a subset of {1,2,…,n}\{1,2, \ldots, n\} such that the value of ∣1−∑i∈Xai∣\left|1-\sum_{i \in X} a_{i}\right| is minimised. Prove that there exists a strictly increasing sequence of nn positive real numbers (b1,b2,…,bn)\left(b_{1}, b_{2}, \ldots, b_{n}\right) with sum equal to 2 such that ∑i∈Xbi=1\sum_{i \in X} b_{i}=1 (New Zealand) Common remarks. In all solutions, we say an index set XX is (ai)\left(a_{i}\right)-minimising if it has the property in the problem for the given sequence (ai)\left(a_{i}\right). Write XcX^{c} for the complement of XX, and [a,b][a, b] for the interval of integers kk such that a⩽k⩽ba \leqslant k \leqslant b. Note that ∣1−∑i∈Xai∣=∣1−∑i∈Xcai∣,\left|1-\sum_{i \in X} a_{i}\right|=\left|1-\sum_{i \in X^{c}} a_{i}\right|, so we may exchange XX and XcX^{c} where convenient. Let Δ=∑i∈Xcai−∑i∈Xai\Delta=\sum_{i \in X^{c}} a_{i}-\sum_{i \in X} a_{i} and note that XX is (ai)\left(a_{i}\right)-minimising if and only if it minimises ∣Δ∣|\Delta|, and that ∑i∈Xai=1\sum_{i \in X} a_{i}=1 if and only if Δ=0\Delta=0. In some solutions, a scaling process is used. If we have a strictly increasing sequence of positive real numbers cic_{i} (typically obtained by perturbing the aia_{i} in some way) such that ∑i∈Xci=∑i∈Xcci\sum_{i \in X} c_{i}=\sum_{i \in X^{c}} c_{i} then we may put bi=2ci/∑j=1ncjb_{i}=2 c_{i} / \sum_{j=1}^{n} c_{j}. So it suffices to construct such a sequence without needing its sum to be 2 . The solutions below show various possible approaches to the problem. Solutions 1 and 2 perturb a few of the aia_{i} to form the bib_{i} (with scaling in the case of Solution 1, without scaling in the case of Solution 2). Solutions 3 and 4 look at properties of the index set XX. Solution 3 then perturbs many of the aia_{i} to form the bib_{i}, together with scaling. Rather than using such perturbations, Solution 4 constructs a sequence (bi)\left(b_{i}\right) directly from the set XX with the required properties. Solution 4 can be used to give a complete description of sets XX that are (ai)\left(a_{i}\right)-minimising for some (ai)\left(a_{i}\right).

Dataset text NuminaMath olympiads. Quoted with source.

Solutions

Official solution Solution 1 by the IMO Problem Selection Committee

The terms of the source let olymmath link to this solution but not copy it. Read the solution (IMO official site).

Similar problems

These problems have the most words in common with this statement.

Locator isl/2019/a3 · Tag 1YREYHPM90 · Edit this page on GitHub · Keys: j next, k previous