MathOverflow Asked on November 3, 2021
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 ?
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.
Answered by Johan Wästlund on November 3, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP