2017 AMC 10A Problem 16

P16-20~3 minPrint

Divisibility & Factors GCD & LCM Bound the quantity above/below or estimate to pin it down Organized listing / direct enumeration

There are 10 horses, named Horse 1, Horse 2, $\ldots$ , Horse 10. They get their names from how many minutes it takes them to run one lap around a circular race track: Horse $k$ runs one lap in exactly $k$ minutes. At time 0 all the horses are together at the starting point on the track. The horses start running in the same direction, and they keep running around the circular track at their constant speeds. The least time $S>0$ , in minutes, at which all 10 horses will again simultaneously be at the starting point is $S=2520$ . Let $T>0$ be the least time, in minutes, such that at least 5 of the horses are again at the starting point. What is the sum of the digits of $T$ ?

Show solution without answering

Key insight

Horse k is at the start at multiples of k minutes. So T is the smallest number divisible by at least five of 1 to 10, which is 12.

Solution

When is a horse at the start? Horse $3$ finishes laps at $3, 6, 9, 12, \ldots$ minutes. In general Horse $k$ is at the start exactly when the time is a multiple of $k$ .
Turn the question around. At time $T$ , the horses at the start are the ones whose numbers divide $T$ evenly. So we want the smallest $T$ that has at least five divisors among $1, 2, \ldots, 10$ . The five horses can be any five, not necessarily Horses $1$ to $5$ .
Try small times. List which horses are at the start:

$T$	Horses at the start	How many
$6$	$1, 2, 3, 6$	$4$
$8$	$1, 2, 4, 8$	$4$
$10$	$1, 2, 5, 10$	$4$
$12$	$1, 2, 3, 4, 6$	$5$

Every other time from $1$ to $11$ has even fewer divisors (a prime like $7$ has only $1$ and $7$ ; $9$ has $1, 3, 9$ ; $4$ has $1, 2, 4$ ). So nothing below $12$ works.
4. At $T = 12$ , Horses $1, 2, 3, 4, 6$ are all at the start. So $T = 12$ .
5. The sum of the digits of $12$ is $1 + 2 = 3$ .

The answer is $\boxed{\textbf{(B)}\ 3}$ .

Why this works

The race track is a story wrapped around divisibility: "Horse $k$ is back at the start" means " $k$ divides the time." Once you see that, the question is just "which small number has many small divisors?" The value $S = 2520$ is a distraction here; it answers the "all ten horses" version.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Horse $k$ is back at the starting point at time $t$ exactly when $t$ is a multiple of $k$ . So at time $T$ the horses at the start are the horses whose numbers divide $T$ , and we want the smallest $T$ with at least five divisors in $\{1, 2, \ldots, 10\}$ .

Any $T \le 11$ has at most four divisors in total ( $6$ , $8$ and $10$ each have exactly four; the primes have two), so none works.

$T = 12$ has divisors $1, 2, 3, 4, 6, 12$ , and five of them are at most $10$ : Horses $1, 2, 3, 4, 6$ are all at the start after $12$ minutes.

So $T = 12$ and the sum of its digits is $1 + 2 = 3$ .

The answer is $\boxed{\textbf{(B)}\ 3}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Introduction to Number Theory, Chapter 3: Multiples and Divisors (§3.3, §3.4, §3.7)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.2)
Introduction to Number Theory, Chapter 5: Divisor Problems (§5.2, §5.3)