John Fremlin's blog: Splitting sticks

A rather nice puzzle with thanks to Mr Chen and Mr B: given a stick of integer length n > 1, split it at an integer point below n, multiply the product of the two pieces and for each piece larger than length 1, do the same thing. What is the sum of all the products?

The answer follows — maybe you would like to take a moment to puzzle it out by yourself?

Firstly, why should the sum of the products not depend at all on the strategy? If one were not restricted to integer divisions in some way, then the strategy would probably become important, depending how the puzzle were then defined. The use of multiplication indicates area; the use of integers indicates blocks. Given that we must have area, we have defined a shape — it should have some symmetry as we can rotate the stick, and balance the increase in one piece of the split with an equal and opposite decrease — thus we guess a triangle.

We therefore present a visualisation of the problem as a triangle with n-1 1x1 blocks all on a line, n-2 blocks above them, n-3 above those stacked from the left until at the top left a single 1x1 block stands. The choice of point to split the stick now resolves to a choice of block on the diagonal - given a choice of such a block k < n, subtract it and the k x k square underneath and to the left of it from the stack of blocks; this leaves up to two triangular piles corresponding to the up to two remaining pieces with length greater than one; each triangle is of the right size so the analogy holds and the answer is the area of the first triangle of blocks: (n-2)(n-1)/2.

Alternatively, one can trivially see it algebraically by induction, but that is less fun.