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

  1. A. Engel, Exploring Mathematics with Your Computer, MAA, 1993

|Contact| |Front page| |Contents| |Store| |Up|

Copyright © 1996-2017 Alexander Bogomolny

 62012864

Search by google: