Game involving points on $[0,1]$

You're given a list of $22$ points in $[0,1]$ (not necessarily distinct), and you're asked to select, at every iteration, $2$ points to be substituted by their midpoint. After $20$ iteration, you should end up with $2$ points. Is there a selection strategy that leads to $2$ points that are at most $10^{-3}$ apart independently of the distribution of the initial list? For $n$ starting points, what would be the optimal distance between the final $2$ points that one could achieve?

Solution 1:

Consider the $n$-tuples ${\bf a}_n:=(0,0,\ldots,0,1)\in[0,1]^n$. I claim that for these ${\bf a}_n$ the optimal final distance $d_n$ is given by $$d_n={1\over 2^{n-2}}\ .$$ Proof. This is certainly true for $n=2$. Assume that it is true for an $n\geq2$, and consider ${\bf a}_{n+1}$. At the first step of the process we can either average a $0$ with $1$, or average two zeros. Using the first option we arrive at ${\bf a}_n'=(0,0,\ldots,0,{1\over2})\in[0,1]^n$, and using the second option we arrive at ${\bf a}_n$. It follows that $$d_{n+1}=\min\{{1\over2}d_n,d_n\bigr\}={1\over2}d_n\ .$$ Therefore the best "universal" constant $\delta_n$ is $\geq{1\over 2^{n-2}}$. It is easily checked that $\delta_3={1\over2}$ (here the optimal strategy is to first average the extreme $x_k$). The following figure shows the optimal end result for the quadruple $(0,x,y,1)$. We can learn two things from this figure: When $n=4$ then we can always obtain a final difference $d\leq0.25={1\over 2^2}$, which implies $\delta_4={1\over4}$, and, more important: Things get very complicated with increasing $n$.

For $n=5$ one cannot draw such a figure. Instead one can do the following: Denote by $g(x,y,z)$ the optimal end result for the quintuple $(0,x,y,z,1)$. The following figure shows the $121$ graphs of the functions $$g\left({j\over10},{k\over10},z\right)\qquad(0\leq z\leq 1)$$ for $0\leq j\leq 10$, $\>0\leq k\leq 10$. The figure supports the conjecture $\delta_5={1\over 8}$. Exact computation gives $$g(0,0,0)={1\over8},\qquad g\left(0,0,{3\over4}\right)={1\over8}\ .$$

Solution 2:

This is not a complete answer but just an example in which the distance between two final points is always greater than $\delta_n=\frac{1}{2^{n-2}}$.

In fact, let $n$ be an even number. Consider an n-tuple $(0,\ldots,0,1-\varepsilon,1)$ with $\varepsilon=\frac{1}{2^{n/2-2}}$. Note that the sum of all numbers after $i$th iteration is at least $(2-\varepsilon)/2^i$; therefore, two final points cannot be closer than $(2-\varepsilon)/2^{n-2}=(2+o(1))\delta_n$ if in some iteration we take the midpoint of two nonzero points.

Therefore, what we have to do on every move is either to cancel one of the zeros or to divide one of nonzero numbers by two. Then, we end up with two points $\frac{1}{2^p}$ and $\frac{1-\varepsilon}{2^q}$ with $p+q\leqslant n-2$. For sufficiently large $n$, the minimum of $\left|\frac{1}{2^p}-\frac{1-\varepsilon}{2^q}\right|$ is attained when $p=q=n/2-1$, and this minimum equals $\frac{\varepsilon}{2^{n/2-1}}=\frac{1}{2^{n-3}}=2\delta_n$.

I hope this technique can lead to a much better lower bound being generalized to deal with the case of many nonzero points.

UPD1. Now I noted that this answer exploits the same idea as Erik's comment on Christian Blatter's answer.

UPD2. As TonyK pointed out in the comment, the tuple $(0,0,0,0,5/7,1)$ has a lower bound of $1/14$ for distance between final points.