Conjetura del corredor solitario

Ejemplo de la conjetura del corredor solitario con 6 corredores

En teoría de números y, especialmente en el estudio de aproximaciones diofánticas, la conjetura del corredor solitario es una conjetura debida originalmente a J. M. Wills en 1967. Las aplicaciones de la conjetura en las matemáticas son variadas; incluyen problemas de obstrucción de visión y cálculo del número cromático de grafos distancia y grafos circulantes. L. Goddyn le dio, en 1998, su pintoresco nombre a la conjetura.

La conjetura

Consideremos k corredores en una pista circular de largo unidad. En t = 0, todos los corredores están en la posición inicial y empiezan a correr; las velocidades de los corredores son distintas dos a dos. Se dice que un corredor está solitario en el tiempo t si está a una distancia de al menos 1/k de cualquier otro corredor en el tiempo t. La conjetura del corredor solitario afirma que cada corredor está solo en algún momento.

Una reformulación útil del problema es asumir que los corredores tienen velocidades enteras, no divisibles todas ellas por el mismo primo; el corredor que estará solo tiene velocidad cero. La conjetura afirma entonces que para cualquier conjunto D de k − 1 enteros posibles con mcd 1,

$\mathrm{\exists }t\in ℝ\mathrm{\forall }d\in D||td||\ge \frac{1}{k},$

donde ||x|| denota la distancia del número real x al entero más cercano.

Resultados conocidos

Si la conjetura del corredor solitario puede ser probada para k≥8 es un problema matemático no resuelto.

k	probado en el año	probado por	notas
1	-	-	trivial: t = 0; cualquier t
2	-	-	trivial: t = 1 / (2 * (v1-v0))
3	-	-	Cualquier prueba para k>3 también prueba k=3
4	1972	Betke and Wills; Cusick	-
5	1984	Cusick and Pomerance; Bienia et al.	-
6	2001	Bohman, Holzman, Kleitman; Renault	-
7	2008	Barajas and Serra	-

Enlaces externos

• Artículo en The Open Problem Garden