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!

---

For those who want actual numbers rather than a mere existence proof, here is iceweasel's answer:

This Haskell program

main=mapM_((putStr "slowdowns 1+1/">>).print.head).iterate(>>= (\l->[a:l|a<-[1..headl-1],all(\b->a*(a+1)`mod`(b-a)==0)l])).map(:[])$[1..]

outputs solutions for numbers of horsemen from 2 to 10 (1 is always included):

slowdowns 1+1/[1]
slowdowns 1+1/[1,2]
slowdowns 1+1/[1,2,3]
slowdowns 1+1/[2,3,4,5]
slowdowns 1+1/[8,9,10,11,12]
slowdowns 1+1/[20,23,24,25,26,27]
slowdowns 1+1/[54,55,56,57,59,60,63]
slowdowns 1+1/[720,727,728,734,735,740,741,755]
slowdowns 1+1/[470280,470287,470294,470295,470300,470301,470303,470304,470315]