[HN Gopher] The lonely runner conjecture
___________________________________________________________________
The lonely runner conjecture
Author : xk3
Score : 79 points
Date : 2022-11-06 18:19 UTC (4 hours ago)
(HTM) web link (en.wikipedia.org)
(TXT) w3m dump (en.wikipedia.org)
| tromp wrote:
| This reminds me of an interesting puzzle about horsemen riding
| around a circular track:
| https://blog.tanyakhovanova.com/2011/03/the-horsemen-sequenc...
| [deleted]
| sanj wrote:
| Is the lonely runner a proxy for the overloaded server in a load
| balancer using consistent hashing?
|
| Or are the pictures just similar?
| squaredot wrote:
| I like very much this conjecture: easy to grasp, with some
| intuition you can understand why it is plausible to hold. No
| general method has been discovered to settle the matter, only
| proofs for specific cases (up to 7 runners apparently).
| gweinberg wrote:
| Isn't it true that if the runners' speeds are all real numbers
| which are not rational multiples of each other, eventually you'll
| see every distribution of positions of the runners, or at least
| come arbitrarily close?
| impendia wrote:
| I believe that if the runners speeds are all real numbers which
| are linearly independent over the rationals, then the
| associated dynamical system will be ergodic
|
| https://en.wikipedia.org/wiki/Ergodicity
|
| and what you say is true.
|
| But in addition to your example you have to worry about, e.g.
| sqrt(2), sqrt(3), and sqrt(2) + sqrt(3).
| contravariant wrote:
| I agree that it's probably ergodic, but to show every
| distribution will definitely come about (approximately)
| you'll need a slightly stronger property than just
| ergodicity. Ergodicity guarantees it is _almost always_ the
| case, but if you want it to always be the case you 'll need
| it to be uniquely ergodic.
|
| Since irrational rotations are uniquely ergodic I reckon this
| system will also be, but I think the proof won't be trivial.
| jameshart wrote:
| The challenge isn't to find sets of numbers that guarantee
| loneliness will occur- as you say, arbitrary reals that aren't
| rational multiples should accomplish that handily. The
| conjecture isn't _that such sets can be found_ - it 's much
| stronger: that if the runners have _any_ set of distinct
| speeds, then they all experience loneliness.
|
| And, according to the article, and perhaps surprisingly:
|
| > The conjecture can be reduced to restricting the runners'
| speeds to positive integers: If the conjecture is true for _n_
| runners with integer speeds, it is true for _n_ numbers _(sic)_
| with real speeds.
|
| i.e., the conjecture is that _n_ runners with speeds which _are
| all_ rational multiples of one another will experience
| loneliness.
| JadeNB wrote:
| > > The conjecture can be reduced to restricting the runners'
| speeds to positive integers: If the conjecture is true for n
| runners with integer speeds, it is true for n numbers ( _sic_
| ) with real speeds.
|
| No need for _sic_ when quoting Wikipedia; you can (and I
| have) just fix it!
| karmakaze wrote:
| The conjecture is stronger: real != rational
|
| > This convention is used for the rest of this article.
| Wills' conjecture was part of his work in Diophantine
| approximation, the study of how closely fractions can
| approximate irrational numbers.
|
| I couldn't have imagined that we might make a connection
| between integers and irrational/real numbers.
| gweinberg wrote:
| Yeah sure I understand that. Just wanted to verify that at
| the offset we can elimate an uncountable number of
| possibilities and so for each n there are only a countable
| number of cases that need to be considered.
| tromp wrote:
| That seems true, by induction on the number of runners. But the
| conjecture does allow for rational speed ratios.
| [deleted]
___________________________________________________________________
(page generated 2022-11-06 23:00 UTC)