KGS math club/solution 11 5
We'll start with a small solution (e.g. three horses or two horses), and show how to build up solutions with any number of horses (including 9).
Suppose two horses have integer speeds and
with
(think of them as laps per day, or whatever you like, the name of the time period doesn't matter). Assume the horses start together at the wide section of track, then the faster horse will do exactly
laps of the course in the day, and the slower does exactly
laps -- so it does
extra laps. This means the faster horse has met/overtaken the slower horse exactly
times (including this final meeting at the end of the day). These meetings will be equally spaced over the day (by symmetry -- for example by running time backwards). These
meeting times will be:
so for these meetings to match up with the times the faster horse is back at the wide section of track we need these times to be inside the list
, i.e.
needs to divide
perfectly. This condition is also enough to guarantee the two horse only ever meet back at the start. We need this property to hold separately for every pair of horses in the race.
Suppose now we have a list of (different, and non-zero) speeds that work (like {1,2} for two horses, or {3,4,6} for three horses) and call it: for
horses. This means that we know that for every pair
and
we know
divides
exactly an integer number of times. We will find a list of speeds with instead
different horse speeds.
Let be the lowest common multiple (the smallest number that all the
divide). In fact we could just use the product
if you're feeling lazy. Then since all speeds
and
divide
perfectly, then so does
for all pairs of speeds. And since
divides
for all
and
, we deduce that
divides
for all
and
.
Now let's magically consider the new set of speeds:
And we claim this is a new sequence with
horses which satisfies the desired properties.
We can notice that for any two speeds in the list, and
, their difference which is
does indeed divide
perfectly. And if we chose speeds
and
instead, then the difference is
which also divides
perfectly.
So we've taken a list of distinct speeds, which satisfy the property that the difference between every pair divides the bigger of the two numbers and made ourselves a longer list (one more element) which also satisfies this property!
We can use this to find a list of 9 horses which do what's required. Suppose we start with {1,2} then S=2 and next we get {2,3,4}.
and if you've got a big enough calculator you'll be able to keep going as far as 9! This is where you might get lazy and use
at each stage instead of having to work out the lowest common multiple at every stage, the drawback is that the numbers in your list are going to grow rather fast!