Una prueba hábil relacionada con la elección de puntos de un intervalo para

Question

Elija un punto en cualquier lugar del intervalo unitario $[0, 1]$ . Ahora elige un segundo punto del mismo intervalo para que haya un punto en cada mitad, $[0, \frac12]$ y $[\frac12, 1]$ . Ahora elige un tercer punto para que haya un punto en cada tercio del intervalo, y así sucesivamente. ¿Hasta cuándo puedes elegir puntos así?

En otras palabras, ¿cuál es la mayor $n$ para que exista una secuencia (finita) $(a_i)_{i=1}^n$ de manera que para todos $k$ entre los primeros $k$ puntos $(a_i)_{i=1}^k$ hay al menos uno en cada intervalo $[0, \frac1k], [\frac1k, \frac2k], \ldots, [\frac{k-1}k,1]$ ?

Mi pregunta

¿Hay alguna prueba de que $n$ ¿está acotado? (Obsérvese que por compacidad, la existencia de tal secuencia para todo $n$ equivale a la existencia de una secuencia infinita con la misma propiedad).

Historia de fondo

Hace poco estuve releyendo viejas columnas de Martin Gardner, y describe este problema en "Solitario búlgaro y otras tareas aparentemente interminables". (Columna original de 1983, disponible en sus colecciones "Las últimas recreaciones: ..." y "El colosal libro de matemáticas"). Dice que el problema apareció por primera vez en "Cien problemas de matemáticas elementales", de Hugo Steinhaus. Allí demuestra que existe una secuencia de longitud 14, pero no hay ninguna de longitud 75. La primera prueba publicada de la secuencia más larga, que tiene una longitud de 17, fue realizada por Elwyn Berlekamp y Ron Graham en su artículo "Irregularities in the distributions of finite sequences" en el Journal of Number Theory. A continuación, Mieczysaw Warmus publicó una prueba más breve en "A supplementary note on the irregularities of distributions" en la misma revista.

Ahora bien, estas pruebas utilizan en su mayoría el análisis de casos en un grado u otro. Son de diversa complejidad, curiosamente con la prueba de Warmus del óptimo $n$ siendo el más corto. Tampoco es muy difícil escribir un control informático que encuentre el óptimo $n$ . Sin embargo, creo que debido a la naturaleza elegante del problema, debería haber alguna prueba "bonita", no de optimalidad, sino simplemente de que dicha secuencia no puede continuar para siempre. ¿Puede alguien encontrar una?

Nota técnica : El problema se suele plantear con intervalos medio abiertos. Yo los hice cerrados para que la compacidad funcionara. ( Editar: La posibilidad de que esto cambie la respuesta sí se me ocurrió. Supongo que no lo hace, y lo comprobaré por ordenador pronto. Me parecen bien las respuestas para cualquier tipo de intervalo: abierto, cerrado, semiabierto).

Answer 1

La prueba dada por Steinhaus (siguiendo a A. Schinzel) es realmente hábil. Voy a parafrasear lo que hace:

En el paso número $n$ el intervalo (0,1) se divide en $n$ intervalos $I_0^{(n)}=(0,\frac{1}{n}), \ldots, I_{n-1}^{(n)}=(\frac{n-1}{n},1)$ . Entonces $\lfloor nP \rfloor$ le da el número del intervalo al que un punto $P$ en la secuencia pertenece al $n.$ paso.

Procede a probar la siguiente afirmación:

Si $P_1 \in (\frac{7}{35},\frac{8}{35})$ y $P_2 \in (\frac{9}{35}, \frac{10}{35})$ entonces hay algo de $n \in \mathbb{N}$ lo suficientemente grande como para que $\lfloor (n-1)P_1 \rfloor < \lfloor nP_1 \rfloor$ pero $\lfloor (n-1)P_2 \rfloor = \lfloor nP_2 \rfloor$ .

Veamos cómo esta afirmación implica que no existe una secuencia infinita de este tipo. Finalmente, en su secuencia en el $k.$ paso habrá dos puntos $P_1,P_2$ como en la reclamación. Sea $n$ ser como en la demanda, en particular $n>k$ .

Dejemos que $k_1:=\lfloor (n-1)P_1\rfloor$ y $k_2:=\lfloor (n-1)P_2\rfloor$ . Entonces $P_i$ pertenece a la $k_i$ . intervalo en el $(n-1).$ nes y hay $k_2-k_1-1$ puntos de $a_1, \ldots, a_{n-1}$ de la secuencia intermedia. Pero en el $n.$ paso, $P_1$ se trasladará al $k_1+1$ .st intervalo, mientras que $P_2$ permanecerá en el $k_2$ .st intervalo, por lo que habrá una ''colisión'' de los puntos intermedios.

Answer 2

La inexistencia de una secuencia infinita se desprende de un resultado de van Aardenne-Ehrenfest sobre la discrepancia de secuencias. No sé si existe una prueba de su teorema. El resultado apareció como T van Aardenne-Ehrenfest, Proof of the impossibility of a just distribution of an infinite sequence over an interval, Proc Kon Ned Akad Wetensch 48 (1945) 3-8.