For any nonempty, finite set $B$ and real $x$, define $$d_B(x) = \min_{b\in B} |x-b|$$ (1) Given positive integer $m$. Find the smallest real number $\lambda$ (possibly depending on $m$) such that for any positive integer $n$ and any reals $x_1,\cdots,x_n \in [0,1]$, there exists an $m$-element set $B$ of real numbers satisfying $$d_B(x_1)+\cdots+d_B(x_n) \le \lambda n$$ (2) Given positive integer $m$ and positive real $\epsilon$. Prove that there exists a positive integer $n$ and nonnegative reals $x_1,\cdots,x_n$, satisfying for any $m$-element set $B$ of real numbers, we have $$d_B(x_1)+\cdots+d_B(x_n) > (1-\epsilon)(x_1+\cdots+x_n)$$
Problem
Source: China TST 2023 Problem 14
Tags: inequalities, Sets
jk2845
31.03.2023 23:49
sketch for a solution for (2): Let N be very big. Let $1<a_{1}<a_{2}<...<a_{N}<2$. Now let $t$ be very big. Now take the $x_{i}$'s to be all whole numbers inside the intervalls $[t^{a_{j}}, t^{a_{j}} + t^{2-a_{j}}]$. To prove that this works, we use that these intervalls have almost the same sums, and that these intervalls are very far away from one another.
CANBANKAN
01.04.2023 09:23
The answer is $\frac{1}{4m-2}$.
Construction of xj'sWe pick $n=2m-1, x_j = \frac{j-1}{2m-2}$ for $j=1,\cdots,2m-1$.
We say $b_j$ covers $x_k$ if $\text{min}_t |b_t-x_k| = |b_j-x_k|$. If there are two $t$'s satisfying this, we pick the smaller $t$. This means each $x_k$ is covered by exactly one $b_j$.
If $b_j$ covers $d_j$ $x_t$'s, then $\sum_{x_t \text{is covered by } b_j} |x_t-b_j| \ge \max_{x_t \text{is covered by } b_j} x_t - \min_{x_t \text{is covered by } b_j} x_t = \frac{d_j-1}{2m-2}$. Since $d_1+\cdots+d_m=2m-1$, it readily follows that $$\sum_{j=1}^{2m-1} d_B(x_j) = \sum_{j=1}^m \sum_{x_t \text{ is covered by } b_j} |x_t-b_j| \ge \sum_{j=1}^m \frac{d_j-1}{2m-2} = \frac{m-1}{2m-2}$$
Since each $x_k$ is covered by exactly one $b_j$ implies $d_1+\cdots+d_m=2m-1$.
Construction of BI claim at least one of $$B_1 = \{ 0, \frac{2}{2m-1}, \cdots, \frac{2(m-1)}{2m-1}\}, B_2 = \{ \frac{1}{2m-1}, \cdots, \frac{2(m-1)+1}{2m-1} = 1\}$$
Works. In fact, I show that $ d_{B_1}(x_j)+d_{B_2}(x_j) = \frac{1}{2m-1}$ for all $1\le j\le n$. Note that if $\frac{a}{2m-1} \le x_j < \frac{a+1}{2m-1}$, then $$d_{B_1}(x_j)+d_{B_2}(x_j) = (x_j-\frac{a}{2m-1}) - (\frac{a+1}{2m-1}-x_j) = \frac{1}{2m-1}$$
This shows that $$\min\{ \sum d_{B_1}(x_j), \sum d_{B_2}(x_j)\} \le \frac 12 \sum (d_{B_1}(x_j)+ d_{B_2}(x_j)) = \frac{1}{4m-2}$$
Let our multiset $\{x_j\}$ contain $N^k$ copies of $N^{T-k}$ for $k=1,\cdots,T$, where $T,N$ are large constants depending on $m$ and $\epsilon$. We set $N > \frac{4}{\epsilon}$ and $T > \frac{2m}{\epsilon}$
Claim: For any $x\in \mathbb{R}$, there exists at most one $k$ such that $|x-N^k| < \frac{N-2}{N} N^k$
Proof: Suppose $|x-N^k| < \frac{N-2}{N} n^k,$ and $ |x-N^l| < \frac{N-2}{N} N^l$ where $l>k$ are integers. Then $$N^l-N^k \le |x-N^l|+|x-N^k| \le \frac{N-2}{N} (N^k+N^l)$$
Which is false.
We say $k$ haORZhe if there exists $x\in B$ such that $|x-N^k| < \frac{N-2}{N}$. By our claim, at least $T-m$ numbers are not haORZhe. Thus,
\begin{align*}
&\sum d_B(x_j) \\
&= \sum_{j=1}^T N^{T-j} d_B(N^j) \\
&\ge \sum_{j \text{ not haORZhe }} N^{T-j} d_B(N^j) \\
&\ge \sum_{j \text{ not haORZhe }} N^{T-j} \frac{N-2}{N} N^j \\
&=\frac{N-2}{N} \cdot N^T \sum_{j \text{ not haORZhe }} 1 \\
&\ge (1-\epsilon/2) (T-m)N^T \\
&\ge (1-\epsilon/2)^2 TN^T \\
&\ge (1-\epsilon) \sum_{j=1}^t N^{T-j}N^j
\end{align*}
zewsx00
02.04.2023 18:43
Thanks for Baby cabbage helping me to solve this problem! For(1),it's similar to above solving by Canbankan. For(2),we let $ k>2^{2\times\left\lceil\log_{1/2}{\varepsilon}\right\rceil+5m}$ For$S_k=\left \{ 0,1,2,…,k \right \} $ We set$n=2^{k+1}-1$and$ x_i=2^{-1-\left \lfloor \log_{2}{i} \right \rfloor }$ We suppose that$B=\left \{ b_1<b_2<…<b_m \right \} $ $T_i=\left [\log_{1/2}{b_i}, \log_{1/2}{b_{i-1} }\right ) $ and$b_0=2^{-k-1} $,$b_{m+1}=1$ Let$I=\left \{ 1\le i\le m+1\mid\left | T_i \right | \ge 2^{\left \lceil \log_{1/2}{\varepsilon } \right \rceil+3m }\right \} $ For$\forall i\in I$ $a=\sup T_i$ $b=\inf T_i$ We have$\left ( 2^{-a},2^{-b}\right ) \cap B=\emptyset $ And\begin{align*} \sum_{j=b}^{a} 2^{j}d_{B}(2^{-j}) &\geq \sum_{j=b+1}^{a} 2^{j}\times \left ( 2^{-j}-2^{-a} \right ) \\ &> a-b-1-2=\left | T_i \right |-3 \\ &>\left ( 1-3\times 2^{-2\times\left\lceil\log_{1/2}{\varepsilon}\right\rceil-3m}\right ) \times \left | T_i \right | \\ &>\left ( 1-\varepsilon \times 2^{2-3m} \right ) \times \left | T_i \right | \\ &> \left ( 1-\varepsilon /2 \right )\times \left | T_i \right | \\ \end{align*}Also \begin{align*} &\sum_{i\in I}\left | T_i \right | \\ &\ge n-m\times 2^{\left\lceil\log_{1/2}{\varepsilon}\right\rceil+3m} \\ &> \left ( 1-m\times 2^{\left\lceil\log_{1/2}{\varepsilon}\right\rceil+3m-k} \right )\times n \\ &=\left ( 1-m\times 2^{-\left\lceil\log_{1/2}{\varepsilon}\right\rceil-2m} \right )\times n \\ &> \left ( 1-\varepsilon \times 2^{-m} \right )\times n \\ &\ge \left ( 1-\varepsilon /2 \right )\times n \end{align*}Therefore\begin{align*} \sum_{k=1}^{n} d_B\left ( x_k \right ) &\ge \sum _{i\in I}\sum _{j\in T_i}2^{j}\times \left ( 2^{-j}-2^{-a} \right ) \\ &> \sum _{i\in I}\left ( 1-\varepsilon /2 \right ) \times \left | T_i \right | \\ &>\left (1-\varepsilon /2 \right )^{2}\times n \\ &>\left ( 1-\varepsilon \right ) \times n \end{align*}Then we are done! $\blacksquare$