Conjetura del corredor solitario

Animación que ilustra el caso de 6 corredores
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[1]​ y cálculo del número cromático de grafos distancia y grafos circulantes.[2]​ L. Goddyn le dio, en 1998, su pintoresco nombre a la conjetura.[3]​

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,

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;[4]​ Cusick[5]​ -
5 1984 Cusick and Pomerance;[6]​ Bienia et al.[3]​ -
6 2001 Bohman, Holzman, Kleitman;[7]​ Renault[8]​ -
7 2008 Barajas and Serra[2]​ -

Referencias

  1. ↑ T. W. Cusick (1973). «View-Obstruction problems». Aequationes Math. 9 (2–3): 165-170. doi:10.1007/BF01832623. 
  2. ↑ a b J. Barajas and O. Serra (2008). «The lonely runner with seven runners». The Electronic Journal of Combinatorics 15: R48. 
  3. ↑ a b W. Bienia et al. (1998). «Flows, view obstructions, and the lonely runner problem». Journal of combinatorial theory series B 72: 1-9. doi:10.1006/jctb.1997.1770. 
  4. ↑ Betke, U.; Wills, J. M. (1972). «Untere Schranken für zwei diophantische Approximations-Funktionen». Monatshefte für Mathematik 76 (3): 214. doi:10.1007/BF01322924. 
  5. ↑ T. W. Cusick (1974). «View-obstruction problems in n-dimensional geometry». Journal of Combinatorial Theory, Series A 16 (1): 1-11. doi:10.1016/0097-3165(74)90066-1. 
  6. ↑ Cusick, T.W.; Pomerance, Carl (1984). «View-obstruction problems, III». Journal of Number Theory 19 (2): 131-139. doi:10.1016/0022-314X(84)90097-0. 
  7. ↑ Bohman, T.; Holzman, R.; Kleitman, D. (2001), «Six lonely runners», Electronic Journal of Combinatorics 8 (2) .
  8. ↑ Renault, J. (2004). «View-obstruction: A shorter proof for 6 lonely runners». Discrete Mathematics 287: 93-101. doi:10.1016/j.disc.2004.06.008. 

Enlaces externos