uniolympiads Ελληνικά

IMC 1997, Day 1, Problem 5

For a natural nn consider the hyperplane

R0n={x=(x1,x2,…,xn)∈Rn:∑i=1nxi=0}R_0^n = \left\{ x = (x_1, x_2, \dots, x_n) \in \mathbb{R}^n : \sum_{i=1}^{n} x_i = 0 \right\}

and the lattice Z0n={y∈R0n:all yi are integers}Z_0^n = \{y \in R_0^n : \text{all } y_i \text{ are integers}\}. Define the (quasi–)norm in Rn\mathbb{R}^n by ∥x∥p=(∑i=1n∣xi∣p)1/p\|x\|_p = \left(\sum_{i=1}^{n} |x_i|^p\right)^{1/p} if 0<p<∞0 < p < \infty, and ∥x∥∞=max⁡i∣xi∣\|x\|_\infty = \max_i |x_i|.

a) Let x∈R0nx \in R_0^n be such that

max⁡ixi−min⁡ixi≤1.\max_i x_i - \min_i x_i \le 1.

For every p∈[1,∞]p \in [1, \infty] and for every y∈Z0ny \in Z_0^n prove that

∥x∥p≤∥x+y∥p.\|x\|_p \le \|x + y\|_p.

b) For every p∈(0,1)p \in (0, 1), show that there is an nn and an x∈R0nx \in R_0^n with max⁡ixi−min⁡ixi≤1\max_i x_i - \min_i x_i \le 1 and an y∈Z0ny \in Z_0^n such that

∥x∥p>∥x+y∥p.\|x\|_p > \|x + y\|_p.
Original from the official PDFFor a natural n consider the hyperplane R 0 n = ( n x = (x 1 , x 2 , . . . , x n ) ∈ R : n X i=1 x i = 0 ) and the lattice Z 0 n = {y ∈ R 0 n : all y i are integers}. Define the (quasi–)norm n 1/p P if 0 < p < ∞, and kxk ∞ = max |x i |. in R n by kxk p = |x i | p i i=1 a) Let x ∈ R 0 n be such that max x i − min x i ≤ 1. i i For every p ∈ [1, ∞] and for every y ∈ Z 0 n prove that kxk p ≤ kx + yk p . b) For every p ∈ (0, 1), show that there is an n and an x ∈ R 0 n with max x i − min x i ≤ 1 and an y ∈ Z 0 n such that i i kxk p > kx + yk p . 5

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. a) For x=0x = 0 the statement is trivial. Let x≠0x \ne 0. Then max⁡ixi>0\max\limits_i x_i > 0 and min⁡ixi<0\min\limits_i x_i < 0. Hence ∥x∥∞<1\|x\|_\infty < 1. From the hypothesis on xx it follows that:

i) If xj≤0x_j \le 0 then max⁡ixi≤xj+1\max\limits_i x_i \le x_j + 1.

ii) If xj≥0x_j \ge 0 then min⁡ixi≥xj−1\min\limits_i x_i \ge x_j - 1.

Consider y∈Z0ny \in Z_0^n, y≠0y \ne 0. We split the indices {1,2,…,n}\{1, 2, \ldots, n\} into five sets:

I(0)={i:yi=0},I(+,+)={i:yi>0,xi≥0},I(+,−)={i:yi>0,xi<0},I(−,+)={i:yi<0,xi>0},I(−,−)={i:yi<0,xi≤0}.\begin{gathered} I(0) = \{i : y_i = 0\}, \\ I(+,+) = \{i : y_i > 0, x_i \ge 0\}, \quad I(+,-) = \{i : y_i > 0, x_i < 0\}, \\ I(-,+) = \{i : y_i < 0, x_i > 0\}, \quad I(-,-) = \{i : y_i < 0, x_i \le 0\}. \end{gathered}
As least one of the last four index sets is not empty. If I(+,+)≠∅I(+,+) \ne \emptyset or I(−,−)≠∅I(-,-) \ne \emptyset then ∥x+y∥∞≥1>∥x∥∞\|x + y\|_\infty \ge 1 > \|x\|_\infty. If I(+,+)=I(−,−)=∅I(+,+) = I(-,-) = \emptyset then ∑yi=0\sum y_i = 0 implies I(+,−)≠∅I(+,-) \ne \emptyset and I(−,+)≠∅I(-,+) \ne \emptyset. Therefore i) and ii) give ∥x+y∥∞≥∥x∥∞\|x + y\|_\infty \ge \|x\|_\infty which completes the case p=∞p = \infty.

Now let 1≤p<∞1 \le p < \infty. Then using i) for every j∈I(+,−)j \in I(+,-) we get ∣xj+yj∣=yj−1+xj+1≥∣yj∣−1+max⁡ixi|x_j + y_j| = y_j - 1 + x_j + 1 \ge |y_j| - 1 + \max\limits_i x_i. Hence

∣xj+yj∣p≥∣yj∣−1+∣xk∣p for every k∈I(−,+) and j∈I(+,−).|x_j + y_j|^p \ge |y_j| - 1 + |x_k|^p \text{ for every } k \in I(-,+) \text{ and } j \in I(+,-).
Similarly
∣xj+yj∣p≥∣yj∣−1+∣xk∣p for every k∈I(+,−) and j∈I(−,+);|x_j + y_j|^p \ge |y_j| - 1 + |x_k|^p \text{ for every } k \in I(+,-) \text{ and } j \in I(-,+);
∣xj+yj∣p≥∣yj∣+∣xj∣p for every j∈I(+,+)∪I(−,−).|x_j + y_j|^p \ge |y_j| + |x_j|^p \text{ for every } j \in I(+,+) \cup I(-,-).
Assume that ∑j∈I(+,−)1≥∑j∈I(−,+)1\sum\limits_{j \in I(+,-)} 1 \ge \sum\limits_{j \in I(-,+)} 1. Then
∥x+y∥pp−∥x∥pp=∑j∈I(+,+)∪I(−,−)(∣xj+yj∣p−∣xj∣p)+(∑j∈I(+,−)∣xj+yj∣p−∑k∈I(−,+)∣xk∣p)+(∑j∈I(−,+)∣xj+yj∣p−∑k∈I(+,−)∣xk∣p)≥∑j∈I(+,+)∪I(−,−)∣yj∣+∑j∈I(+,−)(∣yj∣−1)+(∑j∈I(−,+)(∣yj∣−1)−∑j∈I(+,−)1+∑j∈I(−,+)1)=∑i=1n∣yi∣−2∑j∈I(+,−)1=2∑j∈I(+,−)(yj−1)+2∑j∈I(+,+)yj≥0.\begin{aligned} &\|x + y\|_p^p - \|x\|_p^p \\ ={}& \sum_{j \in I(+,+) \cup I(-,-)} (|x_j + y_j|^p - |x_j|^p) + \left(\sum_{j \in I(+,-)} |x_j + y_j|^p - \sum_{k \in I(-,+)} |x_k|^p\right) \\ &+ \left(\sum_{j \in I(-,+)} |x_j + y_j|^p - \sum_{k \in I(+,-)} |x_k|^p\right) \\ \ge{}& \sum_{j \in I(+,+) \cup I(-,-)} |y_j| + \sum_{j \in I(+,-)} (|y_j| - 1) \\ &+ \left(\sum_{j \in I(-,+)} (|y_j| - 1) - \sum_{j \in I(+,-)} 1 + \sum_{j \in I(-,+)} 1\right) \\ ={}& \sum_{i=1}^n |y_i| - 2 \sum_{j \in I(+,-)} 1 = 2 \sum_{j \in I(+,-)} (y_j - 1) + 2 \sum_{j \in I(+,+)} y_j \ge 0. \end{aligned}
The case ∑j∈I(+,−)1≤∑j∈I(−,+)1\sum\limits_{j \in I(+,-)} 1 \le \sum\limits_{j \in I(-,+)} 1 is similar. This proves the statement.

b) Fix p∈(0,1)p \in (0,1) and a rational t∈(12,1)t \in (\frac12, 1). Choose a pair of positive integers mm and ll such that mt=l(1−t)mt = l(1 - t) and set n=m+ln = m + l. Let

xi=t,i=1,2,…,m;xi=t−1,i=m+1,m+2,…,n;yi=−1,i=1,2,…,m;ym+1=m;yi=0, i=m+2,…,n.\begin{aligned} &x_i = t, \quad i = 1, 2, \ldots, m; \quad x_i = t - 1, \quad i = m+1, m+2, \ldots, n; \\ &y_i = -1, \quad i = 1, 2, \ldots, m; \quad y_{m+1} = m; \quad y_i = 0, \ i = m+2, \ldots, n. \end{aligned}
Then x∈R0nx \in R_0^n, max⁡ixi−min⁡ixi=1\max\limits_i x_i - \min\limits_i x_i = 1, y∈Z0ny \in Z_0^n and
∥x∥pp−∥x+y∥pp=m(tp−(1−t)p)+(1−t)p−(m−1+t)p,\|x\|_p^p - \|x + y\|_p^p = m(t^p - (1-t)^p) + (1-t)^p - (m - 1 + t)^p,
which is possitive for mm big enough.

Transcribed from the official solutions, pages 6–7. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?