# I solved this math puzzle, but I can't remember how. **URL:** \ **Category:** Factual Questions\ **Created:** [November 23, 2015, 4:03am UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338 "2015-11-23T04:03:50Z")\ **Posts on this page:** 15\ **Page:** 1
**Author:** ![kaylasdad99](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/kaylasdad99/32/3398_2.png) [@kaylasdad99](https://boards.straightdope.com/u/kaylasdad99)\ **Post date:** [November 23, 2015, 4:03am UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338/1 "2015-11-23T04:03:50Z")
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) ---
**Author:** ![Giles](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/giles/32/60_2.png) [@Giles](https://boards.straightdope.com/u/Giles)\ **Post date:** [November 23, 2015, 5:09am UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338/2 "2015-11-23T05:09:33Z")
The number of atoms in those molecules at each level are [tetrahedral numbers](https://en.wikipedia.org/wiki/Tetrahedral_number) ---
**Author:** ![Jragon](https://avatars.discourse-cdn.com/v4/letter/j/e19b73/32.png) [@Jragon](https://boards.straightdope.com/u/Jragon)\ **Post date:** [November 23, 2015, 5:14am UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338/3 "2015-11-23T05:14:32Z")
The formula for the any molecule of size n is: Sum from i = 1 to n ( Sum from j = 1 to i (j) ) Sum from j = 1 to i (j) is (1/2)\*(i^2 + i), so with some algebra, we can rewrite our original expression as 1/2 \* [Sum from i = 1 to n (i^2) + Sum from i = 1 to n (i)] = 1/2 \* [n\*(n+1)_(2n+1)/6 + n_(n+1)/2], which works out to what you got with a little algebra and elbow grease. I had to look up the definition of the summation over i^2, since I couldn’t remember it and can’t recall how to rederive it off the top of my head. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [November 23, 2015, 8:48am UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338/4 "2015-11-23T08:48:37Z")
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. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [November 23, 2015, 9:51am UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338/5 "2015-11-23T09:51:43Z")
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.” ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [November 23, 2015, 3:08pm UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338/6 "2015-11-23T15:08:10Z")
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. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [November 23, 2015, 9:41pm UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338/7 "2015-11-23T21:41:44Z")
> [@Chronos](#): > > 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](https://en.wikipedia.org/wiki/Lagrange_polynomial) is easier for modest sizes by hand, and a _lot_ more efficient for large polynomials, especially if you use fast polynomial multiplication, etc. ---
**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\ **Post date:** [November 23, 2015, 10:20pm UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338/8 "2015-11-23T22:20:30Z")
And another way, since I just derived it myself: 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. ---
**Author:** ![kaylasdad99](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/kaylasdad99/32/3398_2.png) [@kaylasdad99](https://boards.straightdope.com/u/kaylasdad99)\ **Post date:** [February 27, 2018, 11:38am UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338/9 "2018-02-27T11:38:26Z")
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? ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [February 27, 2018, 3:27pm UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338/10 "2018-02-27T15:27:40Z")
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.]](http://molgen.de/download/pubs/MathCombChemSCCE.pdf), 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). ---
**Author:** ![kaylasdad99](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/kaylasdad99/32/3398_2.png) [@kaylasdad99](https://boards.straightdope.com/u/kaylasdad99)\ **Post date:** [February 27, 2018, 5:36pm UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338/11 "2018-02-27T17:36:00Z")
> [@DPRK](#): > > 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). Use _what_, now? What, exactly, does [sub]k[/sub] represent? > [@](#): > > 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. 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. > [@](#): > > Real-world usefulness? Depends what you mean- beyond mathematics and beyond three dimensions? E.g., [[Gruener et al.]](http://molgen.de/download/pubs/MathCombChemSCCE.pdf), 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). 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. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [February 27, 2018, 6:14pm UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338/12 "2018-02-27T18:14:12Z")
> [@kaylasdad99](#): > > Use _what_, now? What, exactly, does [sub]k[/sub] represent? 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 1 + 4 + 9 + ⋯ + n[sup]2[/sup] = (n+1)n(n-1)/3 + (n+1)n/2 - 0. So, sure, some ink is used up and you might still call this brute force, but there is no need to count 165 atoms, except perhaps to check your work. ---
**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\ **Post date:** [February 27, 2018, 9:45pm UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338/13 "2018-02-27T21:45:08Z")
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]. Then: c[sub]0[/sub] = a[sub]0[/sub] c[sub]1[/sub] = -(11/6) a[sub]0[/sub] + 3 a[sub]1[/sub] - (3/2) a[sub]2[/sub] + (1/3) a[sub]3[/sub] c[sub]2[/sub] = a[sub]0[/sub] - (5/2) a[sub]1[/sub] + 2 a[sub]2[/sub] - (1/2) a[sub]3[/sub] c[sub]3[/sub] = -(1/6) a[sub]0[/sub] + (1/2) a[sub]1[/sub] - (1/2) a[sub]2[/sub] + (1/6) a[sub]3[/sub] It’s slightly cleaner, but no less clear, written as a matrix equation. ---
**Author:** ![g8rguy](https://avatars.discourse-cdn.com/v4/letter/g/7cd45c/32.png) [@g8rguy](https://boards.straightdope.com/u/g8rguy)\ **Post date:** [February 28, 2018, 12:21am UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338/14 "2018-02-28T00:21:04Z")
> [@ftg](#): > > 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](https://en.wikipedia.org/wiki/Lagrange_polynomial) is easier for modest sizes by hand, and a _lot_ more efficient for large polynomials, especially if you use fast polynomial multiplication, etc. 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] + _a_ _x_[sup]2[/sup] + _b_ _x_ + _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 = 2_a_ + _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. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [February 28, 2018, 12:34am UTC](https://boards.straightdope.com/t/i-solved-this-math-puzzle-but-i-cant-remember-how/738338/15 "2018-02-28T00:34:36Z")
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 O O O O OO OO OO OOO OOO OOOO