lonely runner conjecture

[invite6c250b59]

Bonjour,

Formulation du problème:
Soit k + 1 coureurs autour sur une piste circulaire de longueur 1. Tous les coureurs sont initialement au même point de départ et courent à différentes vitesses, par commodité des entiers distincts sans facteur commun. Un des coureur a une vitesse de 0. La conjecture est qu'à un moment donné tous les autres coureurs seront à une distance d'au moins 1/(k + 1) de lui.

Résolution triviale:
Chaque coureur, quelle que soit sa vitesse >0, passe k/(k+1) de son temps loin et 1/(k+1) de son temps proche de n'importe quel point, quel que soit ce point. Comme il y a k coureurs autres que le coureur de vitesse 0, alors au total ils ne peuvent être proche de lui que k/(k+1) du temps, le laissant seul au moins 1/(k+1) du temps.

Conclusion triviale:
Il y a un truc que j'ai pas compris

Est-ce que quelqu'un pourrait m'expliquer la subtilité manquée?
-----

[invite705d0470]

Franchement, je ne sais pas résoudre ce problème ( Dirichlet semble pointer le bout de son nez, mais ...).
Par contre, je ne comprends pas totalement votre raisonnement :/ je suis d'accord avec la découpe du temps (et donc de la piste, à un facteur près car vt= distance parcourue) mais comment sommez vous ? Parce que si ce raisonnement est vrai pour un coureur, l'est il, par extension, pour k coureurs ? (vitesses différentes, donc a priori on ne considère pas le même point)

[invite6c250b59]

je ne comprends pas totalement votre raisonnement :/ je suis d'accord avec la découpe du temps (et donc de la piste, à un facteur près car vt= distance parcourue) mais comment sommez vous ? Parce que si ce raisonnement est vrai pour un coureur, l'est il, par extension, pour k coureurs ? (vitesses différentes, donc a priori on ne considère pas le même point)

Par construction il existe un cycle (de durée 1 par convention) à l'intérieur duquel tous les coureurs débutent et finissent en même temps. La vitesse de chaque coureur étant constante, on en déduit que tous les coureurs passent un temps identique à l'intérieur de chaque segment de piste. (un coureur passe d'autant moins temps dans ce segment à chaque tour de piste qu'il est rapide, mais s'il est plus rapide il va aussi faire plus de tours par cycle ce qui compense exactement)

Alors après comment sommer?
- supposons qu'en tout temps on a au maximum un seul et unique coureur proche du point de départ (c'est faux par construction mais permet d'utiliser un tout bête principe du pigeonnier): le premier coureur passe 1/(k+1) du temps près du point de départ, le second prend ensuite le relais ce qui porte le total à 2/(k+1) du temps, puis le 3ème pour un total de 3/(k+1) etc etc jusqu'au k^ième et dernier qui porte la somme totale à k/(k+1) du temps où un coureur est proche du point de départ. Celui-ci est donc esseulé au minimum 1/(k+1) du temps.
- supposons qu'il y a des chevauchements, alors toujours par principe du pigeonnier cela signifie que la durée d'esseulement augmente. Comme par construction il y a des chevauchements (à minima au début et à la fin de chaque cycle), alors le point de départ est esseulé de façon strictement plus grande que 1/(k+1) du temps.

Franchement, je ne sais pas résoudre ce problème

Franchement, j'espère moins une résolution du problème qu'une aide à comprendre en quoi ma formulation/résolution du problème est fausse. Quelques liens sur le sujet, et un avertissement:

So beware: read on only if you are prepared to spent hours thinking about a problem that is simple to state, has been open for forty-five years, and has resisted the efforts of some of the top researchers in the world. You have been warned.

http://rjlipton.wordpress.com/2012/0...er-conjecture/
http://rjlipton.wordpress.com/2012/0...ure-an-attack/
http://rjlipton.wordpress.com/2012/0...second-attack/

[invitea07f6506]

Votre raisonnement est faux, mais plus d'un point de vue quantitatif que qualitatif. Il dit bien quelque chose, mais quelque chose de plus faible que ce que vous annoncez.

Un coureur est esseulé si aucun autre coureur n'est à moins de 1/(k+1) de lui. C'est à dire qu'aucun coureur n'est à moins de 1/(k+1) devant ou derrière lui, ce qui interdit une zone de largeur 2/(k+1). Le principe de pigeonnier ne s'applique plus.

Pour prendre un exemple concret, si un coureur est immobile, et tous les k autres coureurs vont à la même vitesse et sont équirépartis le long de la piste, alors à tout moment il y aura un coureur à distance au plus 1/(2k) du coureur immobile. Bien entendu, vu que les hypothèses de la conjecture ne sont pas satisfaites, ce n'est pas étonnant que ses conclusions ne le soient pas non plus. Cependant, votre raisonnement, lui, s'applique toujours (au moins du point de vue du coureur immobile)... Et vous "montrez" alors quelque chose de faux.

Ce que vous démontrez, c'est que la conjecture du coureur isolée est vraie si on remplace 1/(k+1) par 1/(2k). Ce n'est pas la première fois que je vois, en théorie des nombre, un résultat facile à démontrer (ici par le principe du pigeonnier), alors que ses améliorations quantitatives ne le sont pas.

[A voir en vidéo sur Futura]

[invite6c250b59]

Un coureur est esseulé si aucun autre coureur n'est à moins de 1/(k+1) de lui. C'est à dire qu'aucun coureur n'est à moins de 1/(k+1) devant ou derrière lui, ce qui interdit une zone de largeur 2/(k+1).

Ce que vous démontrez, c'est que la conjecture du coureur isolée est vraie si on remplace 1/(k+1) par 1/(2k). Ce n'est pas la première fois que je vois, en théorie des nombre, un résultat facile à démontrer (ici par le principe du pigeonnier), alors que ses améliorations quantitatives ne le sont pas.

Merci beaucoup pour le coup de main