Invariant sum from coin splits

This brainteaser considers a process where a large pile of identical items is repeatedly split into smaller groups, and each split generates a product of group sizes that is added to a running total. The splitting continues until only single items remain, and the puzzle asks for the final sum of all these products, with the twist that the answer must not depend on how the splits are chosen. It is a clean, structure-focused problem, typical of general quant brainteasers and math contest puzzles, that forces the candidate to see through the apparent procedural complexity to a simple underlying combinatorial quantity.

Solving it leans heavily on invariance, recursive reasoning, and careful counting of object pairs. Strong answers usually reformulate the process as counting how often certain relationships between items are "broken" by a split, or set up a recurrence that reveals a closed form independent of the partition path. An interviewer looks for an ability to abstract away from the step-by-step procedure, identify the right invariant, argue that each elementary event is counted exactly once, and express the conclusion succinctly and rigorously.

What it tests

This problem class is governed by the principle of invariance under recursive partitioning, where the total sum of all cross-group products over all splits depends only on the initial group size, not the splitting sequence. The key is that every unordered pair of objects (coins) is separated exactly once at some stage, and each such separation contributes exactly 1 to the sum. Thus, the total sum counts the number of unordered pairs, which is $n(n-1)/2$. This pattern holds because the process recursively decomposes the group, but the sum of all 'cross terms' (products of split sizes) over all possible splits always accounts for every pair exactly once, regardless of the order or structure of the splits. The recurrence relation formalizes this, but the underlying reason is the combinatorial fact that every pair is split once and only once.