Start with a non-empty pile of N counters. A move consists in splitting a pile into two non-empty parts. Repeat the process by applying the moves to thus obtained piles. The process ends when there is no pile left with more than a single counter.

Theorem

Every process described above that starts with a pile of n counters ends in n - 1 steps.

Proof #1 (by induction)

  1. If there are just two counters we clearly need just one split.
  2. Assume that for numbers 1<m<N we have already shown that it takes exactly (m - 1) splits to separate a pile consisting of m counters. Let there be a pile of N counters. Split it into two with m1 and m2 counters, respectively. Of course, m1 +  m2 = N. By the induction hypothesis it will take (m1 - 1) breaks to split the first pile and (m2 - 1) to split the second one. The total will be 1 + (m1 - 1)  + (m2 - 1)  = N - 1.

Remark

In the proof by induction the quantity N - 1 might appear to have come out of the blue. However, there is a justification. Realization that the number of splits only depends on the size of a pile leads to the equation

f(m + n) =  f(m) + f(n) + 1

which I rewrite as g(m + n)  = g(m) + g(n), where g(n) = f(n) + 1. g is an additive integer function and thus is bound to be linear.

Proof #2 (detecting an invariant)

Let start counting how many piles we have after a number of splits. The important observation is that every time we split a pile the total number of piles is grows by 1. (For one bigger pile is being replaced with two smaller ones.) When there is no piles to split, each pile consists of a single counter. At the beginning (after 0 splits) we had 1 pile. After 1 split we got 2 piles. As I said earlier, increasing the number of splits by one increases the number of piles by 1. Therefore, the latter is always greater by one than the former.


Copyright © 1997 Alexander Bogomolny