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).
Is it just me? I really hate how the problem is phrased on that page. Here's the original:
"33 horsemen are riding in the same direction along a circular road. Their speeds are constant and pairwise distinct. There is a single point on the road where the horsemen can pass one another. Can they ride in this fashion for an arbitrarily long time?"
Here's a quick take on how I would rephrase it:
"33 horsemen are riding in the same direction along a circular road. There is just a single point on the road where any number of horsemen can pass each another; everywhere else, a faster rider coming up behind a slower rider will be stuck and have to slow down. Is there a set of pairwise distinct speeds the horsemen can ride at such that the riders can all start at the passing point, ride constantly at their given speed for an arbitrarily long time, and only meet each other at the passing point (thus never having to change speed)?"
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?
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.
> > 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!
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.
> 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.
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
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.
You don't have any smooth movement in consistent hashing. And you can pick your inputs carefully, instead of worrying about the worst case like in the linked conjecture.
> n runners on a track of unit length, with constant speeds all distinct from one another, will each be lonely at some time—at least 1/n units away from all others.
Interesting conjecture! And okay, a lot of interesting problems end up being distilled into tangible if eccentrically named things. Like the "dining philosophers" in computer science to describe deadlock. I'm curious how this relates to a tangible problem.
> Implications
Nice, here we go!
> Suppose C is a n-hypercube of side length s in n-dimensional space.
A hypercube is just the higher-dimensional analog of a cube. A 2-hypercube is a square, a 3-hypercube is a cube, and so on.
Edit: I know complaining about downvotes is against the rules, and I’m not complaining, because I really don’t care about my karma on this site — but I am really confused and curious how people could possibly be opposed to me explaining a mathematical concept to someone who expressed frustration at not knowing it.
It's like that in most fields though. A builder is interesting in applications to buildings. An economist is interested in applications to the economy. Few people see things all the way through, whatever that even means.
The deterministic state of a computation block (aka, a computer) is 2^N where N is the total number of state-retaining elements plus inputs. Large portions of this space are inaccessible due to mutex conditions (e.g., two or more conditions that cannot be true at the same time).
How does an open curve on the edge of an N-dimensional hypercube (snake in the box, as you provided) describe the state of my computer? Your link said nothing about that.
Apologies, the link was intended to go to the image of the hypercube + binary representation (which is much more intuitive than the images Wikipedia displays on the hypercube page), but it failed on mobile: https://upload.wikimedia.org/wikipedia/commons/2/2c/Snake_in...
