Breaking Chocolate Bars: Statements and Proofs

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)

If there are just two counters we clearly need just one split.
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 m₁ and m₂ counters, respectively. Of course, m₁ + m₂ = N. By the induction hypothesis it will take (m₁ - 1) breaks to split the first pile and (m₂ - 1) to split the second one. The total will be 1 + (m₁ - 1) + (m₂ - 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. The 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 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.

Proof #2'

Let's again start with a pile of counters. Mark an arbitrary counter and say "one". Split the pile into two. Of the two smaller piles one will contain the marked counter, while the other will not. Choose an arbitrary counter in the latter and say "two". Now you have two plies, each with a marked counter. Continue the process of splitting the piles. Note that each pile that undergoes the splitting operation has a single marked counter, so that of the splitting operation it is inhereted by one of the smaller ones. Mark an arbitrary counter in the other pile and say ... what? The number you have to utter is exactly the number of marked counters. The process stops when all counters are marked, in which case each of them constitutes a 1-counter pile. (This is because every pile with more than 1 counter contains at most one marked counter.)

Proof #2''

Instead of counting the number of the splittings count the number of piles in front of you. At the outset, there is just one pile. Say "one". After one splitting, there are two piles. So say "two". When there are no piles to split, there are exactly N piles each containing a single counter. Note that, with every split, the number of piles grows by 1. Therefore, the number of splits is 1 less than the number of piles. At the end of the day, when there are N single counter piles, N - 1 split have been performed.

71536037