Let $n$ be a positive integer and let $T$ denote the collection of points $(x_1, x_2, \ldots, x_n) \in \mathbb R^n$ for which there exists a permutation $\sigma$ of $1, 2, \ldots , n$ such that $x_{\sigma(i)} - x_{\sigma(i+1) } \geq 1$ for each $i=1, 2, \ldots , n.$ Prove that there is a real number $d$ satisfying the following condition: For every $(a_1, a_2, \ldots, a_n) \in \mathbb R^n$ there exist points $(b_1, \ldots, b_n)$ and $(c_1,\ldots, c_n)$ in $T$ such that, for each $i = 1, . . . , n,$ \[a_i=\frac 12 (b_i+c_i) , \quad |a_i - b_i| \leq d, \quad \text{and} \quad |a_i - c_i| \leq d.\]
Problem
Source: Turkey National Olympiad 2002 - D2 - P3
Tags: induction, algebra unsolved, algebra
motal
13.03.2011 19:42
I shall prove the result by induction on $n$. The base case is trivial. Suppose the result holds for $h\le n-1$. We notice that when we're given $ (a_{1}, a_{2},\ldots, a_{n})\in\mathbb{R}^{n} $ we can find the required $b$'s and $c$'s iff we can find the required $b$'s and $c$'s when the given $a$'s are, let's say, non-decreasing. In fact, it suffices to permute $b$'s and $c$'s to satisfy that. Hence we can order the $a_i$ so that they're non-decreasing. Let the bound we "found" for $n-1$ be $k$. Now, suppose that we can find an $m$, $1\le m\le n-1$ so that $a_{m+1}-a_m>3k$ (this value $3k$ is rather arbitrary. I chose it so that we can avoid focusing on the limiting cases. I'm sure we could lower the bound if we wished to, like $2k$). Apply the induction hypothesis to $(a_1, a_2, \dots, a_m)$ and $(a_{m+1}, a_{m+2}, \dots, a_n)$ to find $ (b_{1},\ldots, b_{m}) ;\: (c_{1},\ldots, c_{m}) $ and $ (b_{m+1},\ldots, b_{n}) ;\: (c_{m+1},\ldots, c_{n}) $. It's easy to see that $ (b_{1},\ldots, b_{n})$ and $ (c_{1},\ldots, c_{n}) $ satisfy \[\quad |a_{i}-b_{i}| \leq k,\quad\text{and}\quad |a_{i}-c_{i}| \leq k \]
From the induction hypothesis we can find permutations $\pi$ and $\phi$ so that $ b_{\pi(i)}-b_{\pi(i+1) }\geq 1$, with $1\le i\le m-1$ and $ b_{\phi(i)}-b_{\phi(i+1) }\geq 1$, with $m\le i\le n-1$. Moreover $b_{\phi(n)}-b_{\pi(1)}\ge 1$ since we choose a pretty big bound when we said $a_{m+1}-a_m>3k$. Therefore $(b_{\phi(m+1)}, \dots b_{\phi(n)}, b_{\pi(1)}, \dots b_{\pi(m)})$ satisfies the initial condition.
Therefore, if $a_{m+1}-a_m\le3k$, $1\le m\le n-1$ $\Longrightarrow a_n-a_1=(a_n-a_{n-1})+(a_{n-1}-a_{n-2})+\dots +(a_2-a_1)\le 3(n-1)k$. At this point the problem is solved because, when we apply the induction hypothesis on $(a_{1}, a_{2},\ldots, a_{n-1})$ we can eventually choose a suitably large $r>k$ so that $b_n=a_n+r$ and $c_n=a_n-r$. This bound $r$ satisfies the required conditions.