Home > Riddles > The divided loot
A piece of invariants disguised as a distribution: the result seems to depend on the path, but in reality it was fixed from the beginning.
You start with 10 chips in a single pile. In each step you choose a pile, divide it into two non-empty piles, and write down the product of the sizes of those two new piles.
You repeat the process until all the chips are separated, one per pile. At the end you add up all the products that you have been writing down.
What maximum sum can you get? Does it depend on how you do the divisions?
When you divide a heap of size a+b into two heaps of sizes a and b, you write down the product ab. But that product has a very useful interpretation: it counts exactly how many pairs of tiles are separated in that step, one tile on one side and another on the other.
Each pair of pieces in the initial set starts together in the same pile, and throughout the process it is separated only once: right at the step in which, for the first time, its two pieces end up in different piles. Therefore, the sum total of all products is simply the total number of pairs of tokens that were at the beginning.
With 10 tiles, the number of pairs is 10 times 9 divided by 2, or 45. So the final sum is 45 and it does not depend on the order in which you do the divisions.
If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.