Competition problem — Combinatorics

Library / /153 of 196

Combinatorics Difficulty 5.8 AIME, harder Prove it Soviet Union

Problem:

Given non-negative real numbers $a_1$ , $a_2$ , ..., $a_n$ , such that $a_{i-1} \leq a_i \leq 2a_{i-1}$ for $i = 2, 3, \ldots, n$ . Show that you can form a sum $s = b_1 a_1 + \ldots + b_n a_n$ with each $b_i = +1$ or $-1$ , so that $0 \leq s \leq a_1$ .

Solution

Solution:

We show that you can pick $b_n, b_{n-1}, ..., b_r$ so that $s_r = b_n a_n + b_{n-1} a_{n-1} + \ldots + b_r a_r$ satisfies $0 \leq s_r \leq a_r$ . Induction on $r$ .

Trivial for $r = n$ . Suppose true for $r$ . Then $-a_{r-1} \leq s_r - a_{r-1} \leq a_r - a_{r-1} \leq a_{r-1}$ . So with $b_{r-1} = -1$ we have $|s_{r-1}| \leq a_{r-1}$ . If necessary, we change the sign of all $b_n, b_{n-1}, ..., b_{r-1}$ and obtain $s_{r-1}$ as required. So the result is true for all $r \geq 1$ and hence for $r = 1$ .

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 reproduced verbatim; metadata (topic, difficulty) added by this project.