Determine the smallest value of $M$ for which for any choice of positive integer $n$ and positive real numbers $x_1<x_2<\ldots<x_n \le 2023$ the inequality $$\sum_{1\le i < j \le n , x_j-x_i \ge 1} 2^{i-j}\le M$$holds.
Problem
Source: Korea Summer Program Practice Test P7
Tags: inequalities
pokmui9909
04.08.2023 06:04
I got the answer $M = 4044$ in the test. I will post my solution soon.
pokmui9909
04.08.2023 06:40
trivial fact$\sum_{i = 1}^{n}\sum_{j = i + 1}^n \frac{1}{2^{j - i}} = n + \frac{1}{2^{n - 1}} - 2$
Let $S = \{(i, j) | x_j - x_i \geq 1\}, T = \{(i, j) | x_j - x_i < 1\}$
For each $i$, there exists unique integer $l$ such that $x_{i + l} < x_i + 1 \leq x_{i + l + 1}$, let it be $L_i$.
Let $P_k$ be number of $x_i$s in interval $(k - 1, k]$ and $f(x) = \frac{1}{2^x}$.
$\sum_{(i, j) \in T}\frac{1}{2^{j - i}} = \sum_{i = 1}^{n}\left(\frac{1}{2^1} + ... + \frac{1}{2^{L_i}} \right) = \sum_{i = 1}^{n}\left(1 - \frac{1}{2^{L_i}}\right) = n - \sum_{i = 1}^{n}\frac{1}{2^{L_i}}$
Therefore,
$\sum_{(i, j) \in S}\frac{1}{2^{j - i}} = n + \frac{1}{2^{n - 1}} - 2 - \sum_{(i, j) \in T}\frac{1}{2^{j - i}} = \sum_{i = 1}^{n}\frac{1}{2^{L_i}} + \frac{1}{2^{n - 1}} - 2$
$ \leq \sum_{k = 1}^{2023}\left(\frac{1}{2^{0}}+...+\frac{1}{2^{P_k - 1}}\right) + \frac{1}{2^{n - 1}} - 2 = \sum_{k = 1}^{2023}\left(2 - 2\cdot \frac{1}{2^{P_k}}\right) + \frac{1}{2^{n - 1}} - 2 $
$=4044 - 2\left(\frac{1}{2^{P_{1}}} + ... + \frac{1}{2^{P_{2023}}}\right) + \frac{1}{2^{n - 1}}$
$=4044 - 2\left(f(P_1) + ... + f(P_{2023})\right)+ \frac{1}{2^{n - 1}}$
$\leq 4044 - 2\cdot 2023 f\left(\frac{P_1 + ... + P_{2023}}{2023}\right)+ \frac{1}{2^{n - 1}}$ (by Jensen's inequality)
$=4044 - \frac{4046}{2^{\frac{n}{2023}}} + \frac{1}{2^{n - 1}} \leq 4044$
Let $\epsilon > 0$ be arbitrarily small real number and $k$ be positive integer. Let $n = 2023k$.
Consider the case if $a = kq + r (1 \leq r \leq k)$, then $x_a = q + \epsilon a$. Note that $L_a = k - r$.
$\sum_{(i, j) \in S}\frac{1}{2^{j - i}}= \sum_{i = 1}^{n}\frac{1}{2^{L_i}} + \frac{1}{2^{n - 1}} - 2 =\sum_{i = 1}^{2023}\left(\frac{1}{2^0} + ... + \frac{1}{2^{k - 1}} \right) + \frac{1}{2^{2023k - 1}} - 2$
As $\lim_{k \rightarrow +\infty}\left(\sum_{i = 1}^{2023}\left(\frac{1}{2^0} + ... + \frac{1}{2^{k - 1}} \right) + \frac{1}{2^{2023k - 1}} - 2\right) = 4044$, we are done!