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(n2)!+n(n1)!+nn!=n(n1)2+n(n1)3++n(n1)+n+1(n1)!. \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 n1n-1, so n+1n+1 must be divisible by n1n-1, which means 2[=n+1(n1)]2[=n+1-(n-1)] must be divisible by n1n-1. Therefore, n1{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.