Solution to online cake splitting algorithm puzzle.

This is a solution to the cake splitting puzzle posted earlier.

A brief description of the puzzle:

Given a stream of numbers which sum to $1$ and each number being a negative power of $2$, can you give an algorithm to split the numbers in two groups, each of which sum to half when the stream is finished? When you see a number you have to immediately decide which group it goes to. Prove that your algorithm works.

[A more clear description is on the question post].

Solution

---

The algorithm is actually simple: Keep putting the new pieces in group $A$, unless adding that piece will make the sum go over half. In which case, add it to group $B$!

The interesting part is actually proving that it works.

One such proof (thanks to Eigenray of a forums I used to frequent) goes as follows:

Let $R_A$ and $R_B$ be the volumes remaining in each group.

The key property of the algorithm:

When you look at $R_A$ and $R_B$ in binary, if $R_A \ne R_B$ and $R_A \neq 0$, then the ones (or set bits) in $R_A$ all are to the right of the ones in $R_B$.

Let $b$ be the position of left most bit in $B$.

Now suppose the algorithm is adding a piece $2^{-c}$. Now we have that $2^{-c} \le R_A + R_B \lt 2^{-b} + 2^{-(b+1)} + \dots = 2^{-(b-1)}$.

Thus if we cannot add the piece to $A$, we can add it to $B$, and still maintain the property of the bits of $R_B$ being to the left of $R_A$. This property stops holding when $R_A = 0$.