A Board of Stacks That Folds Into a Cube

Take a board of 20 squares by 20. On the square in column $i$ and row $j$, put a stack of $i + j - 1$ unit cubes. The near corner gets one cube, the far corner gets 39, and everything else gets something in between. How many cubes are on the board?

The total is 8000, which is $20^3$. That is not a coincidence and it is not an arithmetic accident. The pile of stacks can be rearranged into a solid cube of side 20, and once you see how, the answer needs no summation at all.

What the stacks actually build

Write $h(i,j)$ for the depth of the stack on square $(i,j)$, with both coordinates running from 1 to $n$.

At $(1,1)$ that is 1 and at $(n,n)$ it is $2n - 1$, so for a board of side 20 the depths run from 1 to 39. The solid is a staircase that rises steadily as you walk in either direction, and its highest ridge runs along the far corner.

The slow route is a correct route

The obvious move is to write the double sum and grind it out. That works. Split the summand and sum each piece over the whole board. Each of $i$ and $j$ runs over $1, \dots, n$ once for every value of the other index, so each contributes $n \cdot \tfrac{n(n+1)}{2}$, and the constant $-1$ contributes $-n^2$.

Nothing about that is wrong. It is worth being blunt on this point, because the temptation when presenting a slicker method is to strike the slow one out, and a strike means the thing is false. The double sum is exact. Its only cost is your time, and under a clock that cost is real, which is a different criticism entirely.

Folding along the squares that are exactly 20 deep

Here is the route that needs no algebra. Pick out the squares whose stack is exactly $n$ deep. By (1) those are the squares with $i + j = n + 1$, and there are $n$ of them, running corner to corner across the board. Now reflect the board across that line.

The consequence is a one-line identity. Any square and its mirror image carry depths that add to the same constant, whatever square you started from.

On the 20 by 20 board every mirror pair adds to 40. The two marked squares in Fig. 1 are 16 deep and 24 deep, and 16 plus 24 is 40. Since the pairing covers the board, with the fold line matched to itself, the depths average exactly $n$ and the total is $n^2$ squares times $n$ deep.

There is a physical version of the same statement that is worth carrying, because it is what makes the word fold honest. Slice the solid flat at height $n$. Some stacks poke above the slice and some fall short of it, and the shortfall at a square is exactly the overhang at its mirror image:

So the material sitting above the slice, moved square by square onto the mirror squares, fills every hole below it with nothing left over and nothing missing. What remains is a slab $n$ by $n$ by $n$.

The fold that proves nothing

A square board has two diagonals and only one of them works, which is where this argument is usually botched. The reflection across the main diagonal is $\tau(i,j) = (j,i)$, and it leaves $i + j$ alone. So $\tau$ pairs every square with a square of the same depth. That is a true symmetry of the solid and it tells you nothing about the total, because pairing equal numbers gives you back the average you were trying to find.

The useful map is the one that reverses depth, and there are two ways to describe it. Either reflect across the anti-diagonal $i + j = n + 1$ as in the definition above, or rotate the board a half turn, $(i,j) \mapsto (n+1-i,\, n+1-j)$. Both send a depth of $h$ to $2n - h$, so either will do. The instruction fold along the diagonal is ambiguous, and half the time it points at the wrong line, which is why it is better to say fold along the squares that are exactly $n$ deep.

A third route: look at the depths themselves

The mean of $i$ over $1, \dots, n$ is $(n+1)/2$, and the same for $j$, so the mean depth over the board is

Multiply by the $n^2$ squares and you get $n^3$ again. This is the fold argument stripped of geometry: what the fold really establishes is that the distribution of depths is symmetric about $n$, and a symmetric distribution has its mean at the centre of symmetry.

The counts in that figure are readable directly from (1). The number of squares with $i + j - 1 = s$ is the number of ways to write $s+1$ as a sum of two indices in range, which is $s$ while $s \le n$ and $2n - s$ after that. They total $n^2$, as they must.

The general statement, and the absence of exceptions

Equations (2), (3) and (6) are all statements about a general $n$, so the identity that the stacks fill a cube is not a fact about 20. It holds for every positive integer $n$, including $n = 1$, where the board is a single square carrying a single cube and $1^3 = 1$. At $n = 2$ the depths are 1, 2, 2, 3, which sum to 8. Nothing needs excluding and no side condition needs stating, which is unusual enough in this kind of problem to be worth saying.

What does change if you perturb the setup is the shape of the answer. Put $i + j - 1$ on a rectangular $m \times n$ board and the mean depth becomes $(m + n)/2$, so the total is $mn(m+n)/2$, which is only a cube when $m = n$. Put $i + j$ on the square board instead and the total is $n^3 + n^2$, since every one of the $n^2$ squares gains a cube. The cube appears because the depth function is linear in both coordinates and centred so that its average lands on $n$ exactly.

Sources and further reading

• The sum used twice in equation (2) — Arithmetic progression
• The pairing argument as a general technique — Double counting and Involution
• The number the total turns out to be — Cube (algebra)
• Why the two diagonals behave differently — Reflection

The total was checked three ways before publication. Symbolic algebra closes the double sum in (2) to $n^3$ for a general $n$. Exhaustive enumeration of every square on every board from $n = 1$ to $n = 40$ agrees with $n^3$ in each case, and on each of those boards the fold was verified to be an involution whose fixed points are exactly the $n$ squares of depth $n$, with every matched pair summing to $2n$. Finally the physical version of (4) was carried out: after moving each overhang onto its mirror square, all $n^2$ squares were confirmed to stand exactly $n$ deep.