El siguiente problema se planteó hace unos años en el concurso alemán de informática para alumnos ("Bundeswettbewerb Informatik"). Originalmente estaba envuelto en una historia que traduzco brevemente a continuación. Mi segunda "traducción" ya incluye mi comprensión del problema en términos de matemáticas puras.
Lo fascinante para mí es lo siguiente: Aunque el problema no menciona ningún número, mi programa informático sólo encontró una solución para 17 tiendas (pero ninguna para 18 y más). Me pregunto si existe una prueba rigurosa para esto.
Consideremos una playa de longitud finita. Durante un período de verano llegan a esta playa varios campistas (uno tras otro). El primer campista puede poner su tienda donde quiera. Cuando llegue el segundo campista, la playa se dividirá en dos partes iguales y el segundo deberá poner su tienda en la mitad libre. Por lo general, si llega el k's campista, la playa se divide en k partes iguales y sólo debe haber una tienda por parte.
La pregunta es la siguiente: Dado que todos los campistas eligen perfectamente sus posiciones, ¿cuántos campistas pueden llegar hasta que no haya forma de añadir otro (además de mover las tiendas)?
Mi traducción matemática supone lo siguiente:
- Las tiendas son puntuales
- La playa tiene un tamaño de 1 (considere los números reales de 0 a 1)
- Si un campista pone su tienda en la posición 0,5 se encuentra por definición en la mitad derecha ([0,5, 1])
- Por lo tanto, también podemos pensar en la playa como el intervalo abierto $[0, 1)$
Para un número natural N dado, ¿existe una forma de elegir una secuencia de puntos (ordenados) $P_1, P_2, \dots, P_N$ en el intervalo $[0, 1)$ tal que para cada $k \in \{1,\dots,N\}$ y cada $l \in \{1, \dots,k\}$ sólo existe una $i \in \{1, \dots, k\}$ tal que
$\frac{l-1}{k} \le P_i < \frac{l}{k}$
Me gustaría saber lo siguiente:
- ¿Existe una solución para cualquier N o hay un N máximo?
- Si hay un máximo N, ¿cuál es?
Investigando este problema sólo pude simplificarlo un poco. Por ejemplo: basta con considerar los "límites" como posibles puntos para las tiendas. Supongamos que se quiere encontrar una solución para $N=4$ (que es bastante fácil :-)). Basta con considerar las siguientes posiciones posibles:
$0, 1/4, 1/3, 1/2, 2/3, 3/4$
Pensando en esto también me vino a la mente Eulers $\varphi$ porque el número de esas posiciones posibles es $\sum_{k=1}^N \varphi(k)$ . Así que el problema podría estar relacionado con los números primos.
Se agradece cualquier pista que apunte a una solución. También me gustaría me gustaría saber si conoce problemas similares o tal vez otras formulaciones del mismo problema.
Enlace al problema original, en alemán (ver página 6): http://www.bundeswettbewerb-informatik.de/uploads/media/bwi23/runde2/aufgaben232.pdf
