Stacking positive and negative cannonballs
Imagine you are a soldier in charge of stacking cannonballs. Your fort has a new commander, a man with OCD who wants the cannonballs stacked in a very particular way.
The new commander wants the balls stacked in tetrahedra. The balls on the bottom of the stack are arranged into a triangle. Then the next layer is also a triangle, each ball resting in the space between balls in the previous layer. Keep doing this until there's one ball on top.
For example, you might have 10 balls on the first layer, 6 on the next layer, then 3, then 1. That's how you'd stack 20 cannonballs.
The number of cannonballs in a tetrahedon n layers high is called the nth tetrahedral number. We just showed that the 4th tetrahedral number is 20.
Not every number is a tetrahedral number, so it's not always possible to stack a given number of cannonballs into a tetrahedron. But it's always possible, as far as we know, to stack any number of cannonballs into no more than five tetrahedra. Usually it is possible to use no more than four tetrahedra. Naturally, your new commander would like the cannonballs arranged into no more than four tetrahedra.
There are two ways of meeting the commander's wishes. One is to make a list of the number of cannonballs that cannot be arranged into four tetrahedral stacks and have a standing order that whenever the cannon fire is over, you always shoot one more ball to avoid having to stack a forbidden number of balls.
The other possibility is to allow the possibility of negative cannonballs.
We explain both possibilities below.
Tetrahedral numbersLet T(n, 2) be the number of cannonballs on the bottom layer of a tetrahedron, arranged into a triangle withh n balls on each side. This is the nth triangular number. The 2 in T(n, 2) stands for two dimensions.
Now let T(n, 3) be the nth tetrahedral number.
It's possible to define and find a compact expression for T(n, d) for all positive integers d, which I wrote about here. But for this post we only need T(n, 3).
Pollock's conjectureSir Frederick Pollock conjectured in 1850 that every positive integer can be written as the sum of at most 5 tetrahedral numbers, and all but a finite number of integers can be written as the sum of at most 4 tetrahedral numbers.
Both parts of the conjecture are still open. Nobody has found a number requiring more than 5 tetrahedral numbers in its sum, and it is believed that there are exactly 241 numbers that cannot be written as the sum of 4 tetrahedral numbers, the smallest being 17 and the largest being 343867. For a list of these numbers, see OEIS sequence A000797.
Negative cannonballsIt is possible to write any integer as the sum of four tetrahedral numbers if you take the formula for computing T(n, 3) as the definition of T(n, 3), which permits negative values of n [1]. Vadim Ponomarenko [2] showed that this could be done and shows how:
Proof: expand the four terms on the right and simplify.
Satisfying the commanderI imagine the commander might not be pleased with the negative cannonball solution. If you could imagine negative cannonballs as balls missing from the stack, that would be one thing, but that's not where we are. To stack 17 cannonballs into four tetrahedra, you'd need a stack of 969 balls, a stack of 680 balls and two stacks of 816 negative balls.
Better go back to saying certain numbers of cannonballs simply aren't allowed, or require a fifth stack. But what if you tell the commander 17 balls cannot be arranged into four tetrahedral stacks and he tells you to try harder.
You could write a Python program to show by brute force when an arrangement isn't possible. Brute force isn't the most elegant approach, but it's often the most convincing. This code will check whether n cannonballs can be stacked in four tetrahedral piles.
def t(n): return n*(n + 1)*(n + 2) // 6def check(n): m = n + 1 s = set() for i in range(m): for j in range(m): for k in range(m): for l in range(m): s.add(t(i) + t(j) + t(k) + t(l)) return n in s
You could be a little more clever by using itertools to eliminate the deeply nested for loops, though this goes against the spirit of brute force.
from itertools import productdef check2(n): m = n + 1 s = set() for i, j, k, l in product(range(m), range(m), range(m), range(m)): s.add(t(i) + t(j) + t(k) + t(l)) return n in s
Update: The code above could be made much more efficient. See the C code in the comment.
Related posts[1] We tend to forget definitions once we have convenient formulas. This an be good or bad. It's bad for comprehension. For example, calculus students usually don't appreciate that the fundamental theorem of calculus is a theorem. They learn to compute integrals by using antiderivatives and come to think that the antiderivative is the definition of an integral.
The upside of blurring definitions and formulas is that it is common to use a formula to generalize a definition, as we do here. This is often a very useful approach, but it has to be done consciously.
[2] Vadim Ponomarenko. Pollock's Generalized Tetrahedral Numbers Conjecture. The American Mathematical Monthly Vol. 128, No. 10 (December 2021), p. 921.
The post Stacking positive and negative cannonballs first appeared on John D. Cook.