Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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!

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=KGS_math_club/solution_11_5&oldid=38484"