21
$\begingroup$

I'm puzzled by the following riddle, which seems easy at first, but turns out to be more complex than it looks. I would like to go to the bottom of it, and could not find references online.

The riddle

You have 9 horses racing on a circular track. they start at the same point, and each of them has a constant speed, but all their speeds are different.

They are only allowed to pass each other at the point of the circle marking their common starting point, otherwise they collide.

Can you choose their speeds so that they can run forever without colliding ?

What I did

After some time I understood that the problem is equivalent to the following: find 9 integers so that the ratio of any two of them can be written $k/(k+1)$ for some integer $k$ (that can depend on the chosen pair).

For instance with 4 horses you can take 6 8 9 12, as 6/8=3/4, 8/12=2/3, and so on.

A solution with 6 horses: 210 216 220 224 225 240.

This constraint can be translated into a condition on the successive differences of the numbers, and we ask that a certain system of modular equations computed from these differences has a solution. The solution is the speed of the slowest horse, and the differences give you the other ones.

Having this, I did a computer bruteforce search on the differences between the integer speeds (with some tricks to fast it up), and managed to get up to 12 horses. Unfortunately I cannot see any structure emerging, which makes me think I missed the point, and another approach could be more explanatory. I'm still not able to explain how to find a solution with 9 horses without the help of a computer.

Question

Is there a solution for any number of horses ?

Improve this question
$\endgroup$
3
  • $\begingroup$ What is your solution of 12 horses? I've only managed to get 9-horse solutions. $\endgroup$
    – LeechLattice
    Jul 19, 2020 at 17:31
  • 20
    $\begingroup$ You want a set where the gcd of two elements equals the absolute value of their difference. If you've found such a set with $n$ elements, then you can find one with $n+1$ elements as follows: Take the lcm of your $n$ elements and add it to each of the $n$ elements; finally take as the $n+1$ element this lcm. E.g. start with $6$, $8$, $9$, $12$ -- their lcm is $72$, and now form $72$, $78$, $80$, $81$, $84$. $\endgroup$
    – Lucia
    Jul 19, 2020 at 18:00
  • 2
    $\begingroup$ @Lucia Nice solution thanks ! If you expand it into an answer I'll accept. $\endgroup$
    – Denis
    Jul 19, 2020 at 18:29

1 Answer 1

Reset to default
1
$\begingroup$

Apologies for commenting in an answer when there is already an answer in the comments...

When I was a PhD-student (in the 90's), we were discussing variations of the van der Waerden theorem on monochromatic arithmetic progressions. A question that came up was whether we can require the monochromatic sequence to consist of consecutive multiples of some number. The answer is no for three-term progressions and two colors, and the counterexample is well-known in the context of the Erdös discrepancy problem: Color the positive integers 1 or 2 according to the last nonzero digit in their base 3 representation.

But it's true for progressions of length 2 and any number of colors, as my then fellow student Gustav Ryd showed us basically using Lucia's construction! For instance, if we have 3 colors, two of the numbers 6, 8, 9, 12 must have the same color, and so on.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.