Splitting piles
Here is the problem:
Given a pile of n chips, n > 1. This pile is randomly split into two piles with, say, k > 0 and (n  k) > 0 chips. The product k(n  k) is computed. A pile with a single chip is called trivial. While there are nontrivial piles, one is selected in random, randomly split into two, the product of the number of chips in the parts is taken and all such products are summed up. By the time only trivial piles are left, the number will be equal to (n  1)n/2 regardless of how the piles have been split.
Proof
Tie each chip to every other chip by a thread. In all, there are going to be (n  1)n/2 threads. When you split a pile into two parts of x and y chips each, you have to cut xy threads connecting chips from the two parts. Which is exactly the number you will add to the total. To reach the stage of no nontrivial piles you will have to cut all the original threads.
(A different proof and a more detailed discussion can be found elsewhere.)
Reference
 A. Engel, Exploring Mathematics with Your Computer, MAA, 1993
Contact
Front page
Contents
Store
Up
Copyright © 19962017 Alexander Bogomolny
