In the Math Corner of my September Diary I borrowed a brainteaser from the 2019 Putnam Competition. (The 2020 Putnam, originally scheduled for February 2020, was canceled on account of the coronavirus.)
Problem: Determine all possible values of the expression
A³ + B³ + C³ − 3ABCwhere A, B, and C are non-negative integers.
I added: "It's harder than it looks, but you can solve it with just basic arithmetic." Well, let's see.
This page actually includes two solutions. The first is mine & of the breaking-rocks type. The second, submitted by a reader, is shorter and smarter.
• My solution
I of course come at this from an empiricist's point of view. What values do you get for that expression, which I shall call P?
P = A³ + B³ + C³ − 3ABC
Microsoft Excel makes it easy to run off a few dozen. I just ran (A, B, C) from (0, 0, 0) to (5, 5, 5), taking advantage of the symmetry in the definition of P. There is no need to distinguish between (5, 0, 2) and (2, 5, 0); both will give the same P.
(That's just the left-hand half of my spreadsheet.)
The first thing you notice is that the P are all non-negative — not what you'd necessarily expect, since the definition of P includes a subtraction. Recall, however, the well-known fact that the arithmetic mean of a set of non-negative numbers is never less than the geometric mean. Applying that to the three numbers A³, B³, and C³: the arithmetic mean is (A³ + B³ + C³) / 3, the geometric mean is the cube root of A³B³C³, which of course is ABC. Since the first can't be less than the second,
(A³ + B³ + C³) / 3 ≥ ABC
it follows that
A³ + B³ + C³ ≥ 3ABC
A³ + B³ + C³ − 3ABC ≥ 0
so P can't be negative.
Now sort on the bottom row of the Excel spreadsheet, then run your eye along that row of Ps.
Not counting repetitions, you see:
0, 1, 2, 4, 5, 7, 8, 9, 10, 11, 13, 14, 16, 18, 20, 27, 28, 32, …
We're missing 3, 6, 12, 15, 21, 24, and 30; all numbers that are multiples of 3 but not of 9. True, we're also missing 17, 19, 22, 25, 26, 29, 31, … The pattern is good up to 16, though, and that's as much as you can reasonably expect from such a small sample. In fact (5, 6, 6) gives P = 17, (6, 6, 7) gives P = 19, (7, 7, 8) gives P = 22, (8, 8, 9) gives P = 25, and so on.
Inspired by that pattern I shall frame a bold hypothesis.
First, I shall divide all the non-negative whole numbers into two classes, Blues and Reds. Blues are multiples of 3 but not of 9; Reds are all the others. I include 0 in the Reds. Hey, it's a multiple of 9: 0 × 9 = 0, right?
Blues: 3, 6, 12, 15, 21, 24, 30, 33, 39, 42, 48, 51, 57, …
Reds: 0, 1, 2, 4, 5, 7, 8, 9, 10, 11, 13, 14, 16, 17, 18, …
A mnemonic for keeping in mind which is which: The Blues are the numbers I suspect are left out — not included in the P party. Who doesn't feel blue when left out?
Here's my bold hypothesis. With dazzling originality, I shall call it "Hypothesis."
Hypothesis: P can take any Red value but no Blue value.
The first part is easier to prove.
- If A, B, and C are all equal, then P = 0. So P can be 0.
- The spreadsheet suggests that when A, B, and C are consecutive integers, P is an exact multiple of 9. (2, 3, 4), for example, gives
P = 27. Yes: If you put (A, B, C) equal to (n, n + 1, n + 2) and work the algebra, you get
P = 9(n + 1). So P can be any exact multiple of 9.
- Following that hint, try (A, B, C) equal to (n, n, n + 1) and work the algebra again. P comes out to 3n + 1. So P
can be any number that leaves remainder 1 after division by 3: 4, 7, 10, 13, 16, …
- Along the same lines, (A, B, C) equal to (n, n + 1, n + 1) gives P equal to 3n + 2. So P can be any number that leaves remainder 2 after division by 3: 5, 8, 11, 14, 17, …
That takes comprehensive care of the Reds. P can be any one of them.
Can P be Blue, though? Can P be a multiple of 3 but not of 9? Hypothesis says it can't. How do I prove that?
I don't know any way to do it without some heavy-duty algebra. However, I can greatly reduce the quantity of that algebra by taking a slight detour.
Start detour: Suppose P is any multiple of 3 — i.e. it may also be a multiple of 9 — I don't care. Then for some non-negative whole number k,
A³ + B³ + C³ − 3ABC = 3k.
A³ + B³ + C³ = 3ABC + 3k.
Plainly the right-hand side is a multiple of 3, so the left-hand-side must be, too.
I just proved that, on the assumption given (i.e. that P is a multiple of 3), A³ + B³ + C³ must also be a multiple of 3. So what?
So this. One little factlet that every seasoned arithmetician carries around with him is this one:
For any whole number m, (m³ − m) is a multiple of 3.
Why is this so? Because (m³ − m) factorizes to m(m² − 1), which further factorizes to m(m − 1)(m + 1), which rearranges to (m − 1)m(m + 1). That's three consecutive whole numbers, so one of them must be a multiple of 3, and so therefore must the product be.
Putting m = 0, 1, 2, 3, 4, 5, 6, 7, for example, gives (m³ − m )= 0, 0, 6, 24, 60, 120, 210, 336. Yep: all divisible by 3.
With that factlet in mind, I shall subtract (A + B + C) from (A³ + B³ + C³). Why? Because the result, after some slight rearranging, is (A³ − A) + (B³ − B) + (C³ − C); and that, by the factlet I just summoned, is a multiple of 3.
And since we have already proved that A³ + B³ + C³ is a multiple of 3, it must be the case that A + B + C is, too. If X − Y is a multiple of 3 and we know that X is, then Y must be, too.
So there's a result: On the assumption I'm working with, that P is a multiple of 3, it must be true that A + B + C is also a multiple of 3.
Now, if I divide any whole number by 3 there are three possibilities for the remainder: 0, 1, and 2. So the remainders for (A, B, C) could be (0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 1), (0, 1, 2), (0, 2, 2), (1, 1, 1), (1, 1, 2), (1, 2, 2), (2, 2, 2). Note that, as before, I am taking advantage of the symmetry. Possibility (2, 0, 1) is not different from possibility (0, 1, 2) in any way that matters to us.
By showing that A + B + C is a multiple of 3, however, I have reduced those ten possibilities to four. The only remainders that leave A + B + C exactly divisible by 3 are (0, 0, 0), (0, 1, 2), (1, 1, 1), and (2, 2, 2).
I shall take each of the four possible remainders sets in turn and grind through the algebra to calculate P.
- Remainders (0, 0, 0): For some whole numbers a, b, c, I have A = 3a, B = 3b, and
C = 3c. Feeding those into the formula for P, I get
P = 27a³ + 27b³ + 27c³ − 81abc.
Plainly P is a multiple of 9; i.e. it's Red!
- Remainders (0, 1, 2): For some whole numbers a, b, c, I have A = 3a, B = 3b + 1,
and C = 3c + 2. Feeding those into the formula for P, I get
P = 27(a³ + b³ + c³ − 3abc) + 27(b² + 2c² − 2ab − ca) + 9(b +4c −2a) + 9.
Which again is a multiple of 9, and so Red.
- Remainders (1, 1, 1): For some whole numbers a, b, c, I have A = 3a + 1,
B = 3b + 1, and C = 3c + 1. Feeding those into the formula for P, I get
P = 27(a³ + b³ + c³ − 3abc) + 27(a² + b² + c² − ab− bc− ca) − 9(a + b + c).
- Remainders (2, 2, 2): For some whole numbers a, b, c, I now have A = 3a + 2,
B = 3b + 2, and C = 3c + 2. Feeding those into the formula for P, I get
P = 27(a³ + b³ + c³ − 3abc) + 54(a² + b² + c² − ab− bc− ca) − 36(a + b + c).
Conclusion: If P is a multiple of 3, it must be a multiple of 9. P cannot be Blue.
As before, I shall call the expression P:
P = A³ + B³ + C³ − 3ABC
P being symmetrical in A, B, and C, I can wolog assume A ≤ B ≤ C.
Let B = A + n and C = A + m, where n and m both belong to (0, 1, 2, …).
Then, after making substitutions and working the algebra:
P = 3A * (n² + m²) + n³ + m³ − 3Anm.
= 3A * (n² + m² − nm) + (n³ + m³)
Factorizing that sum of cubes:
P = 3A * (n² + m² − nm) + (n + m) * (n² − nm + m²)
= (3A + (n+m)) * ((n+m)² − 3nm)
Either (n + m) is a multiple of 3, or it's not.
If it is, then P is a product of two factors each a multiple of 3, so P is a multiple of 9.
If it's not, then P is a product of two factors neither of which is a multiple of 3. P can't then be a multiple of 3.
In the language of my solution, that leaves open the question whether P can take any "red" value. That, however, is the shorter and easier part of my solution. If you just insert it here, my reader's full solution is still way shorter than mine.