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 $y$ and $x$ with $y>x$ (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 $y$ laps of the course in the day, and the slower does exactly $x$ laps -- so it does $y-x$ extra laps. This means the faster horse has met/overtaken the slower horse exactly $y-x$ 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 $n$ meeting times will be: $\frac{1}{y-x}, \frac{2}{y-x}, \ldots, \frac{n}{y-x}=1;$ 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 $\frac{1}{y}, \frac{2}{y}, \ldots, \frac{y}{y}=1$ , i.e. $y-x$ needs to divide $y$ 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: $s_1, s_2, s_3, \ldots, s_n$ for $n$ horses. This means that we know that for every pair $i$ and $j$ we know $s_j-s_i$ divides $s_j$ exactly an integer number of times. We will find a list of speeds with instead $n+1$ different horse speeds.

Let $S=lcm(s_1,s_2,s_3,\ldots,s_n)$ be the lowest common multiple (the smallest number that all the $s_i$ divide). In fact we could just use the product $s_1s_2s_3\cdots s_n$ if you're feeling lazy. Then since all speeds $s_i$ and $s_j$ divide $S$ perfectly, then so does $s_j-s_i$ for all pairs of speeds. And since $s_j-s_i$ divides $s_j$ for all $i$ and $j$ , we deduce that $s_j-s_i$ divides $s_j+S$ for all $i$ and $j$ .

Now let's magically consider the new set of speeds: $S, s_1+S, s_2+S, s_3+S, \ldots, s_n+S.$ And we claim this is a new sequence with $n+1$ horses which satisfies the desired properties.

We can notice that for any two speeds in the list, $s_i+S$ and $s_j+S$ , their difference which is $s_j-s_i$ does indeed divide $s_j+S$ perfectly. And if we chose speeds $S$ and $s_i+S$ instead, then the difference is $s_i$ which also divides $s_i+S$ perfectly.

So we've taken a list of $n$ 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}. $\{2,3,4\} \Rightarrow \{12,14,15,16\} \Rightarrow \{1680,1692,1694,1695,1696\}\Rightarrow \ldots$ 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 $S=s_1s_2\cdots s_n$ 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]

Page

Toolbox

Search

KGS math club/solution 11 5