Maths Olympiad Prep

Track / Stage 5 / 99 of 400 #699 of 1964

Problem 699

AIME late
Number theory Difficulty 5.2 Find the answer

(2004 Czech and Slovak Mathematical Olympiad) Find the positive integer nn, such that n1!+n2!+⋯+nn!\frac{n}{1!}+\frac{n}{2!}+\cdots+\frac{n}{n!} is an integer.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Next problem →

Official solution

12. When n=1,2,3n=1,2,3, the sums are 1,3,51,3,5, respectively, which are integers.

When n>3n>3,
n1!+n2!+⋯+n(n−2)!+n(n−1)!+nn!=n(n−1)⋯2+n(n−1)⋯3+⋯+n(n−1)+n+1(n−1)!. \begin{aligned} & \frac{n}{1!}+\frac{n}{2!}+\cdots+\frac{n}{(n-2)!}+\frac{n}{(n-1)!}+\frac{n}{n!} \\ = & \frac{n(n-1) \cdots 2+n(n-1) \cdots 3+\cdots+n(n-1)+n+1}{(n-1)!} . \end{aligned}

For it to be an integer, the numerator must be divisible by n−1n-1, so n+1n+1 must be divisible by n−1n-1, which means 2[=n+1−(n−1)]2[=n+1-(n-1)] must be divisible by n−1n-1. Therefore, n−1∈{1,2}n-1 \in\{1,2\}, which is impossible.
Thus, the sum is an integer if and only if n∈{1,2,3}n \in\{1,2,3\}.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.