May 2024
—————————
In the Math Corner of my May 2024 Diary I posted the following brainteaser.
This brainteaser is a bit of an old chestnut but worth another airing. I have lifted it from the April 2024 Math Horizons magazine, who tell us that it appeared as problem 2a in the final round of the 2019-2020 Niels Henrik Abel Mathematics Competition in Norway.
Preamble. The word "number" in what follows means "positive whole number greater than zero." Every such number has a factorial, defined as the product of all the numbers less than or equal to itself. The factorial of N, written N! is 1 × 2 × 3 × 4 × 5 × 6 × 7 … × N.
So 1! is just 1; 2! is 1 × 2, which is 2; 3! is 1 × 2 × 3, which is 6; 4! is 1 × 2 × 3 × 4, which is 24; 5! is 1 × 2 × 3 × 4 × 5, which is 120; and so on.
Factorials get big very quickly: 20! is 2,432,902,008,176,640,000; 100! has 158 digits. For big numbers, Stirling's formula gives a good approximation.
(As defined, 0! has no meaning. It's convenient in some branches of math, however, to treat 0! as equal to 1, so you may see that. It isn't relevant here.)
OK, here's a curious fact: 1! + 1! + 2! + 2! = 3!
If a number N has factorial equal to the sum of N + 1 factorials of lesser numbers, I shall call it factorially additive. (Not to be confused with factorwise compliant, heh.) Since 3! is the sum of four lesser factorials, it is factorially additive.
What other numbers besides 3 are factorially additive?
—————————
• Solution.
Here's the equation we seek solutions for:
a1! + a2! + a3! + … aN+1! = N!
In what follows I'll refer to the left- and right-hand sides of that equation as the LHS and RHS respectively.
Key fact number one: N ≥ 3.
Proof: Since there are N+1 terms on the LHS and every one is at least 1, it must be the case that
N+1 ≤ N!. This is not true for N = 1 or N = 2, but it is true for
N ≥ 3. QED.
Key fact number 2: Every a in the LHS is in the range from 1 to N−1 inclusive.
Proof: If any of them were equal to N or more, the LHS would be bigger than the RHS, so no equality. QED.
Key fact number 3: Some unknown number of the a's on the LHS, possibly zero, are equal to N−1. I'll call this
number u. So in the case N = 3, u is 2. Key fact: u < N
Proof: If u was equal to N the LHS would be N(N − 1)! plus some other number
aN+1! to get
the count of a's up to N + 1 That's bigger than N!, so no equality. A fortiori if u is bigger
than N. QED.
Proof that no other numbers besides 3 are factorially additive:
Since u of the a's on the LHS are equal to N−1, the number of a's not equal to it is
N+1−u, and none of them is bigger than (N−2).
So the LHS cannot be bigger than u(N−1)! + (N+1−u)(N−2)!
If we subtract u(N−1)! from that it leaves some number not greater than (N+1−u)(N−2)!
Now subtract u(N−1)! from the RHS. Since the RHS is equivalent to N(N−1)! we are left with (N−u)(N−1)!
Now divide both LHS and RHS by (N−2)! The LHS becomes some number not greater than (N+1−u); the RHS is (N−u)(N−1).
Subtracting (N−u) from both sides, for N to be factorially additive we need the RHS, now reduced to (N−u)(N−2), to be equal to some number not greater than 1. In other words, we need
1 ≥ (N−u)(N−2).
Remembering that u<N (key fact number 3) so that (N−u) is never zero, this is true for N=3, u=2 but never otherwise. QED