Maths Olympiad Prep

Library / /86 of 264

Number theory Difficulty 5.4 AIME, harder Prove it Romania

Let nn be a positive integer. Prove that every integer between 11 and n!n! can be written as the sum of at most nn distinct positive divisors of n!n!.

Solution

We use induction on nn; the base case n=1n=1 is obvious.

Suppose now that the conclusion holds for some positive integer nn and consider m(n+1)!m \le (n+1)!. Then m=(n+1)q+rm = (n+1)q + r, q,rNq, r \in \mathbb{N}, 0rn0 \le r \le n. It is easily noticed that qn!q \le n!, therefore qq can be written as a sum of (at most) nn divisors of n!n! – denote them d1,,dkd_1, \dots, d_k, knk \le n, whence

m=(n+1)d1+(n+1)d2++(n+1)dk+r m = (n + 1)d_1 + (n + 1)d_2 + \dots + (n + 1)d_k + r

and (n+1)di(n+1)d_i are divisors of (n+1)!(n+1)!.
If r=0r = 0, the induction step is finished. Otherwise r>0r > 0, rr divides (n+1)!(n+1)! and r<n+1(n+1)dir < n+1 \le (n+1)d_i, therefore mm can be written as the sum of k+1k+1 distinct divisors of (n+1)!(n+1)!, with k+1n+1k+1 \le n+1 and we are done.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.