Maths Olympiad Prep

Library / /119 of 520

Number theory Difficulty 5.2 AIME, harder Find the answer

12. (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. Spacing and $ signs are ignored.

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.