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$.
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$.
No comments:
Post a Comment