Problem 22 · 2015 AMC 8
Hard
Number Theory
divisor-countinglcm
On June 1, a group of students is standing in rows, with 15 students in each row. On June 2, the same group is standing with all of the students in one long row. On June 3, the same group is standing with just one student in each row. On June 4, the same group is standing with 6 students in each row. This process continues through June 12 with a different number of students per row each day. However, on June 13, they cannot find a new way of organizing the students. What is the smallest possible number of students in the group?
Show answer
Answer: C — 60 students.
Show hints
Hint 1 of 2
Strip away the story: 'students per row' that divides the group evenly is just a divisor of n. Each of the 12 days uses a different one, and running out on day 13 means there are no more — so n has exactly 12 divisors.
Still stuck? Show hint 2 →
Hint 2 of 2
Two clues fix n's prime factors: it's a multiple of 15 and of 6, hence of lcm(6,15) = 30 = 2·3·5. Now use the divisor-count formula — (exponent+1) multiplied across the primes — to grow 30 into something with exactly 12 divisors, as cheaply as possible.
Show solution
Approach: translate the rows into a divisor-counting problem
- A valid 'students per row' must divide n evenly, so each day is a distinct divisor. Twelve days then 'no new way' means n has exactly 12 divisors.
- n is a multiple of 15 and 6, so of lcm(6,15) = 30 = 2·3·5. Its divisor count is (1+1)(1+1)(1+1) = 8 — we need 4 more.
- The divisor count multiplies (exponent+1) over the primes; to push 8 up to 12 = 3·2·2, raise one exponent from 1 to 2. Doing it to the smallest prime is cheapest: 22·3·5 = 60 gives (3)(2)(2) = 12. (Bumping 3 or 5 instead gives 90 or 150 — bigger.)
- Smallest n = 60.
- Why this transfers: 'number of ways to arrange in equal rows' = number of divisors, and you control it through the prime exponents via the (e+1) product — to minimize the number, add the new factor to the smallest prime.
Mark:
· log in to save