Maths Olympiad Prep

Library / /7 of 20

Number theory Difficulty 5.5 AIME, harder Prove it Greece

Determine all pairs (k,n)(k, n) of positive integers satisfying the equation
1!+2!++k!=1+2++n. 1! + 2! + \cdots + k! = 1 + 2 + \cdots + n.

Solution

We first compute the entries of the following matrix

kk12345678910
k!k!126241207205040403203628803628800
1!+2!++k!1!+2!+\cdots+k!139331538735913462334091134037913

Obviously, the pairs (k,n)=(1,1)(k, n) = (1, 1) and (k,n)=(2,2)(k, n) = (2, 2) are solutions. We will show that the unique solution with k>2k > 2 is (k,n)=(5,17)(k, n) = (5, 17).

We observe that since k!k! is divided by 100100 for k10k \geq 10, the sum 1!+2!++k!1!+2!+\cdots+k! leaves a remainder 1313 when divided by 100100 for k9k \geq 9. If equality holds
1!+2!++k!=1+2++n=n(n+1)2 1! + 2! + \cdots + k! = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}
for some k10k \geq 10, then there is some natural number mm such that
n(n+1)=100m+26 n(n + 1) = 100m + 26
or
n2+n100m26=0. n^2 + n - 100m - 26 = 0.
The discriminant is Δ=400m+105\Delta = 400m + 105 and it should be a perfect square. On the other hand we cannot have
x25(mod100), x^2 \equiv 5 \pmod{100},
as otherwise 2525 would divide 55. Therefore the given relation cannot hold for k9k \ge 9, as well as, for k=7k = 7. Since
9=32,153=3217,873=3297 and 46233=3211467, 9 = 3^2, \quad 153 = 3^2 \cdot 17, \quad 873 = 3^2 \cdot 97 \text{ and } 46233 = 3^2 \cdot 11 \cdot 467,
we observe that 2153=18172 \cdot 153 = 18 \cdot 17, a product of two consecutive integers k>2k > 2. Therefore the only solution is (k,n)=(5,17)(k, n) = (5, 17).

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.