Solution to puzzle 116 (A generalization)

Show that any given positive integer less than or equal to n! can be represented as the sum of at most n distinct divisors of n!.

---

We will use mathematical induction on n.

The base case is trivially true for n = 1.

Let a be a positive integer less than or equal to (n + 1)!.
By the division algorithm there exist integers q and r such that a = q(n + 1) + r, with 0 r < n + 1.

Then q n!, and so, by the inductive hypothesis, q can be represented as the sum of at most n distinct divisors of n!.
That is, q = d₁ + d₂ + ... + d_k, with k n.
Hence a = d₁(n + 1) + d₂(n + 1) + ... + d_k(n + 1) + r.
That is, the sum of k + 1 (i.e., at most n + 1) distinct divisors of (n + 1)!.

It follows by induction that any given positive integer less than or equal to n! can be represented as the sum of at most n distinct divisors of n!.

Source: K. Sengupta

Back to top