2005 AMC 10B Problem 22

1. Simplify the sum. $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$. For example, $1 + 2 + 3 + 4 = 10 = \frac{4 \cdot 5}{2}$.
2. Simplify the division. We want
$$\frac{n!}{n(n+1)/2} = \frac{2 \cdot n!}{n(n+1)}.$$
Since $n! = n \cdot (n-1)!$, the $n$ cancels, leaving $\dfrac{2 \cdot (n-1)!}{n+1}$. So the question is: does $n + 1$ divide $2 \cdot (n-1)!$?
3. Try small cases to see a pattern:

The failures happen when $n + 1$ is an odd prime.
4. Why a prime fails. Say $n + 1$ is an odd prime such as $7$. Then $(n-1)! = 5!$ is $1 \cdot 2 \cdot 3 \cdot 4 \cdot 5$, all smaller than $7$. A prime cannot be built from smaller factors, so $7$ does not divide $2 \cdot 5!$.
5. Why everything else works. If $n + 1$ is not prime, split it into two smaller factors, like $12 = 3 \cdot 4$. Both factors are at most $n - 1$, so both appear in $(n-1)! = 1 \cdot 2 \cdots (n-1)$, and their product divides it. If the two factors are the same, as in $9 = 3 \cdot 3$, use $3$ and $6$ instead, both in $1 \cdot 2 \cdots 7$. The only tiny cases, $n + 1 = 2$ and $n + 1 = 4$, were checked in the table.
6. Count. $n + 1$ runs from $2$ to $25$. The odd primes in that range are $3, 5, 7, 11, 13, 17, 19, 23$: eight of them. So $8$ values of $n$ fail and $24 - 8 = 16$ work.

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

Simplify the condition with algebra before testing numbers: here the $n$ cancels and a cleaner question appears. A factorial contains every number smaller than it, so any number built from smaller factors divides it. Primes are the only numbers that cannot be built that way, so they are the only ones that fail. Counting the few failures is easier than counting the successes.

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}$.