Juego que tiene puntos en $[0,1]$

Question

Te dan una lista de $22$ $[0,1]$ (no necesariamente distintos), y se le pedirá que seleccione, en cada iteración, $2$ puntos para ser sustituido por su punto medio. Después de $20$ iteración, usted debe terminar con $2$ puntos. Hay una estrategia de selección que lleva a la $2$ de los puntos que se encuentran en la mayoría de los $10^{-3}$ aparte independientemente de la distribución de la lista inicial? Para $n$ puntos de partida, ¿cuál sería la distancia óptima entre el final de la $2$ puntos que se podría lograr?

Answer 1

Considere la posibilidad de la $n$-tuplas ${\bf a}_n:=(0,0,\ldots,0,1)\in[0,1]^n$. Yo reclamo que por estos ${\bf a}_n$ final óptimo distancia $d_n$ está dado por $$d_n={1\over 2^{n-2}}\ .$$ Prueba. Esto es especialmente cierto para $n=2$. Supongamos que es cierto para una $n\geq2$, y considerar la posibilidad de ${\bf a}_{n+1}$. En el primer paso del proceso podemos promedio de $0$$1$, o un promedio de dos ceros. El uso de la primera opción llegamos a ${\bf a}_n'=(0,0,\ldots,0,{1\over2})\in[0,1]^n$, y el uso de la segunda opción llegamos a ${\bf a}_n$. De ello se sigue que $$d_{n+1}=\min\{{1\over2}d_n,d_n\bigr\}={1\over2}d_n\ .$$ Por lo tanto, la mejor "universal" constante$\delta_n$$\geq{1\over 2^{n-2}}$. Es fácil comprobar que $\delta_3={1\over2}$ (aquí la estrategia óptima es el primer promedio de la extrema $x_k$). La siguiente figura muestra el óptimo resultado final por el cuádruple $(0,x,y,1)$. Podemos aprender dos cosas de esta figura: Al $n=4$ entonces siempre podemos obtener una diferencia final $d\leq0.25={1\over 2^2}$, lo que implica $\delta_4={1\over4}$, y, más importante: las Cosas se ponen muy complicado con el aumento de la $n$.

Para $n=5$ no se puede sacar de tal figura. En su lugar se puede hacer lo siguiente: Denotar por $g(x,y,z)$ el óptimo resultado final para la quíntuple $(0,x,y,z,1)$. La siguiente figura muestra el $121$ gráficas de las funciones $$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}$. El cálculo exacto da $$g(0,0,0)={1\over8},\qquad g\left(0,0,{3\over4}\right)={1\over8}\ .$$

Answer 2

Esto no es una respuesta completa, pero sólo un ejemplo en el cual la distancia entre dos puntos finales es siempre mayor que $\delta_n=\frac{1}{2^{n-2}}$.

De hecho, vamos a $n$ ser un número par. Considere la posibilidad de una n-tupla $(0,\ldots,0,1-\varepsilon,1)$$\varepsilon=\frac{1}{2^{n/2-2}}$. Tenga en cuenta que la suma de todos los números después de $i$th iteración es, al menos,$(2-\varepsilon)/2^i$; por lo tanto, dos puntos finales no puede ser más que $(2-\varepsilon)/2^{n-2}=(2+o(1))\delta_n$ si en alguna iteración tomamos el punto medio de dos distinto de cero puntos.

Por lo tanto, lo que tenemos que hacer en cada movimiento es ya sea para cancelar uno de los ceros o dividir uno distinto de cero de números de dos. Entonces, tenemos dos puntos de $\frac{1}{2^p}$$\frac{1-\varepsilon}{2^q}$$p+q\leqslant n-2$. Por lo suficientemente grande $n$, el mínimo de $\left|\frac{1}{2^p}-\frac{1-\varepsilon}{2^q}\right|$ es alcanzado cuando $p=q=n/2-1$, y este mínimo es igual a $\frac{\varepsilon}{2^{n/2-1}}=\frac{1}{2^{n-3}}=2\delta_n$.

Espero que esta técnica puede conducir a una mejor cota inferior de ser generalizada para tratar el caso de muchos distinto de cero puntos.

UPD1. Ahora he notado que esta respuesta se aprovecha la misma idea como Erik el comentario sobre Cristiano Blatter de la respuesta.

UPD2. Como TonyK se señaló en el comentario, la tupla $(0,0,0,0,5/7,1)$ tiene un límite inferior de $1/14$ con respecto a la distancia entre los puntos finales.