2005 AMC 10B Problem 22

Since $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$, the quotient is
$$\frac{n!}{n(n+1)/2} = \frac{2\,(n-1)!}{n+1}.$$
So we need $n + 1$ to divide $2\,(n-1)!$.

If $n + 1$ is an odd prime $p$: $p$ divides neither $2$ nor any factor of $(n-1)! = (p-2)!$, so the quotient is not an integer. These $n$ fail.

Otherwise: if $n + 1 = 2$ ($n = 1$), the quotient is $2 \cdot 0!/2 = 1$. If $n + 1 = 4$, the quotient is $2 \cdot 2!/4 = 1$. If $n + 1$ is composite and at least $6$, write $n + 1 = ab$ with $1 < a \le b$; if $a < b$ both appear as separate factors in $(n-1)!$, and if $n + 1 = a^2$ with $a \ge 3$ then $a$ and $2a$ both lie in $\{1, \dots, n-1\}$. Either way $n + 1$ divides $(n-1)!$. These $n$ succeed.

The odd primes up to $25$ are $3, 5, 7, 11, 13, 17, 19, 23$: eight values of $n + 1$, hence eight failing $n$. The count of successes is $24 - 8 = 16$.

The answer is $\boxed{\textbf{(C)}\ 16}$.

Simplify the divisibility condition algebraically before testing anything; the factor $n$ cancels and the question becomes "does $n+1$ divide $2(n-1)!$." A prime is the only kind of integer that cannot be assembled from smaller factors inside a factorial, so primes are exactly the obstruction. Counting the failures is much easier than counting the successes.

Under time pressure, test a few values: $n = 2$ ($2!/3$, fails), $n = 3$ ($6/6$, works), $n = 4$ ($24/10$, fails), $n = 5$ ($120/15$, works), $n = 6$ ($720/21$, fails). The failures $2, 4, 6, \ldots$ are exactly those with $n + 1$ prime, which suggests the rule and the count $24 - 8$.

• Missing that n + 1 = 4 and n + 1 = 9 (squares of primes) still work, or forgetting the case n + 1 = 2 works because of the factor 2.
• Counting all primes up to $25$ (nine, including $2$) as failures and answering $15$, or counting primes up to $24$ and mishandling $n = 22$.