Many years ago (more than 26), I picked up a fun little book of Mensa-level puzzles with which to tease my brain and exercise my problem-solving muscles. The final section of the book contained a sort of “practice” Mensa test (because, surprise! the whole book was evidently intended as a Mensa recruiting tool all along).
Anyway, one of the problems contained in the test was a math puzzle that really piqued my interest. It went a little something like this:
Consider a molecule that is constructed in layers. The innermost layer has one atom; the second layer has 1 + 2 atoms; the third layer has 1 + 2 + 3 atoms, etc. If the molecule has one million layers, what is the exact number of atoms in the molecule?
I’m going to have to ask that you take my word for it when I report that I figured out the method for solving the problem within a half hour. The formula is [x[sup]3[/sup] + 3x[sup]2[/sup] + 2x]/6. I don’t mind admitting that I was rather pleased with myself for being able to do that.
In the intervening years, however, I find myself at a loss to remember HOW I accomplished this feat. The formula for the number of atoms in each layer is easy ([x[sup]2[/sup] + x]/2); and it’s not difficult to factor that out from the original formula, leaving [x + 2]/3.
So, how the HELL did I decide to multiply [x + 2]/3 to solve the problem? I’d be grateful for any insights the mathematicians of the Dope can provide.
(P.S. the exact number of atoms in the million-layer molecule is 16,6667,166,667,000,000)
You may or may not have thought about it this way, but this is one way you could approach the problem:
Imagine the layers as broken up into “buckets” like so: in layer L, the first bucket has 1 atom, the second bucket has 2 atoms, and so on, through the last bucket with L atoms.
Then, to specify a particular atom is to specify its layer number L (which can be any number from 1 through the number of layers), then a bucket number B within that layer (where B can be any number from 1 through L), then an atom number A within that bucket (where A can be any number from 1 through B).
Thus, to specify an atom is to give a non-decreasing sequence of three positive integers A <= B <= L, all <= the constant x, where x is the number of layers.
Put another way, to specify an atom is to give a strictly increasing sequence of three positive integers A < B + 1 < L + 2, all <= the constant x + 2.
The number of such sequences (and thus the number of atoms) is the number of ways to pick 3 distinct values from a set of size x + 2. That is, it is “(x + 2) choose 3”, which is (x + 2) * (x + 1) * (x + 0)/(3 * 2 * 1), which comes out to the formula you gave.
You may also have carried out the same reasoning as above, implicitly, by looking at Pascal’s Triangle and thinking “There’s a diagonal line with the values 1, 2, 3, … . The next diagonal line down contains the successive sums of these: 1, 1 + 2, 1 + 2 + 3, …, representing the number of atoms in successive layers. And the next diagonal line down contains the successive sums of these; accordingly, the formula for total number of atoms (as a function of number of layers) is the formula for entries on this last-noted line, which, by the relation between Pascal’s triangle and binomial coefficients, is (x + 2) choose 3, which is (x + 2) * (x + 1) * x/(3 * 2 * 1); done.”
Yet another way to solve the problem: You know that the solution must be a cubic polynomial. So then you just need to know which cubic polynomial it is. Four known points are enough to find that, and it’s not too hard to find the first four.
I’ve used this method a lot in algorithm analysis and such.
But …
Naively, you’re solving a system of linear equations. 2 is okay. 3 is a bit of a pain. 4? Am I really going to start entering stuff into an equation solver? Naive is bad.
Lagrange polynomial interpolation is easier for modest sizes by hand, and a lot more efficient for large polynomials, especially if you use fast polynomial multiplication, etc.
I went in with two things: the formula for triangular numbers (n(n+1)/2, which is also easily re-derived), and the formula for the volume of a pyramid (bh/3).
Since the base is n(n+1)/2, I knew the volume must be something like n(n+1)/2*n/3. It wouldn’t be quite that since we have quantized elements, but it would be close.
The counts in question are 1, 4, 10, 20, etc. Multiply by 3 to get 3, 12, 30, 60. Divide by the triangular numbers (1, 3, 6, 10) to get 3, 4, 5, 6.
That’s good enough for an engineer like me, so I know the formula is n(n+1)(n+2)/6.
I finally remembered how I did it. Brute force. I figured layers up to n=9, and figured tetrahedrons up to 9 layers. Dividing each tetrahedron by the number of units in its largest layer gave me a result that could be expressed as (n + 2)/3.
Frex, in a nine-layer tetrahedron, there are 165 units, and the ninth layer has 45 units. 165/45 can be expressed as (9 + 2)/3; 84/28 (seven layers) when expressed as (7 + 2)/3, etc.
Flush with success, and with a little time on my hands, I decided to brute-force a summation in four dimensions. I succeeded in finding n (n + 1) (n + 2) (n + 3)/4! (that’s not my excitement that I figured it out; that’s 4 factorial). This led me to the realization that I could do this with as many dimensions as anyone could ask for, with the formula n(n + 1)(n + 2)…(n + [z - 2])(n + [z - 1])/z!, where z represents the number of dimensions being considered.
Now, having derived that expression, I have two concerns: first, considering that this works for any value of z down to two, is there a more elegant expression to depict this formula; and second, does this have any real-world usefulness?
And third, I guess, is there a way to express the formula such that it would work in one dimension?
You can type everything into a computer, but it’s easy enough to work out these sorts of sums robotically by hand (i.e., use calculus): let (x)ₖ = x(x-1)…(x-k+1). Then (x+1)ₖ - (x)ₖ = k(x)[sub]k-1[/sub]. So ∑[sub]x≤n/subₖ = (n+1)[sub]k+1[/sub] / (k+1).
Now, 1 + 2 + … + n = ∑[sub]x≤n/sub₁ = ½(n+1)₂ = n(n+1)/2. This is your two-dimensional formula; the one-dimensional sum just equals n.
Next, 1 + (1+2) + (1+2+3) + … (1+…+n) = ∑[sub]x≤n+1[/sub]½(x)₂ = ⅙(n+2)₃ = n(n+1)(n+2)/6 . This is your original expression.
Repeated integration obviously gives (n)[sup]d[/sup]/d!, where (n)[sup]d[/sup] is the rising factorial in case that is more elegant.
Real-world usefulness? Depends what you mean- beyond mathematics and beyond three dimensions? E.g., [Gruener et al.], if you start with the molecule cubane triacid chlorine and attach increasing numbers of amino acids starting with the 4 active sites, then there are 1, 5, 15, 35, 70, 126, etc. ways to do this (4-d case).
Use what, now? What, exactly, does [sub]k[/sub] represent?
Sorry, calculus never got installed in my brain. I recognize that integrals/integration and derivatives/differentiation and limits are words associated with calculus, but the instant someone starts actually doing it in front of me, I’m as lost as I am when people talk about television shows that I’d need HBO to watch (is Tyrion Lannister pissed off at Tony Soprano for ordering a hit on his favorite dragon? And what does Cersei Lannister have against Carrie Bradshaw, anyway? And why is Sookie Stackhouse never seen in the same place as Lorraine Calluzzo?).
I figured out my formulae using just algebra, and that’s all I’m prepared to deal with.
That’s what I’m talking about! Cool!
I wonder if doing this in even higher dimensions will be the key to FTL, or String Theory, or time travel, or something.
Well, maybe not time travel. That usually ends up with the universe never having existed, or something.
Actually, you can pretty much ignore the word “calculus” — all I did above is a bit of algebra that needs no analysis, limits, differentiation, or some such to perform.
All I was trying to say is that you can easily work out any sum p(1) + p(2) + ⋯ + p(n) , where p is a polynomial, by slightly re-writing it: instead of A + Bx + Cx[sup]2[/sup] + ⋯ manipulate it so that it looks like A’ + B’ x + C’ x(x-1) + D’x(x-1)(x-2) + ⋯, which is straightforward if you start from the highest power of x. For example,
x[sup]2[/sup] = x(x-1) + x.
The reason is that if p(x) = q(x+1) - q(x), then p(1) + ⋯ + p(n) = q(2) - q(1) + q(3) - q(2) + ⋯ + q(n+1) - q(n) = q(n+1) - q(1). So, for example, if p(x) = x[sup]2[/sup], then you can take q(x) = x(x-1)(x-2)/3 + x(x-1)/2. Thanks to this mindless symbolic manipulation, we know that
Here’s another approach that while straightforward, may lack clarity…
Suppose you have a[sub]0[/sub], a[sub]1[/sub], a[sub]2[/sub], a[sub]3[/sub] such that a[sub]i[/sub] = p(i) where p(n) is the third degree polynomial p(n) = c[sub]0[/sub] + c[sub]1[/sub] n + c[sub]2[/sub] n[sup]2[/sup] + c[sub]3[/sub] n[sup]3[/sup].
But in this case, you can reduce it down to 2 almost immediately.
[ul]
[li] You know the number of atoms on layer x is 1/2 x (x+1).[/li][li] Then the total number of atoms up through and including those on layer x must by 1/6 (x[sup]3[/sup] + ax[sup]2[/sup] + bx + c). That is, you know the coefficient of x[sup]3[/sup] must be 1/6 by referring back to the Euler-Maclaurin formula.[/li][li] You also know the total number of atoms through zero layers is 0, so c = 0.[/li][/ul]
So you’re just solving a 2x2 set of equations:
1 = 1/6 (1 +* a* + b)
4 = 1/6 (8 + 4 a + 2 b).
These obviously simplify to
5 =a + b
8 = 2a + b,
the solution to which can simply be read off.
Or you could just use the Euler-Maclaurin formulas for the whole thing, of course.
For the 3d case, at least, it can also help to slice it differently. Instead of standing the tetrahedron on a face, stand it on the edge. For a tetrahedron that’s 4 on an edge, for instance, that gives you layers of
Cool!