You want to evenly split a cake of volume one between two people, say $A$ and $B$, so that each gets the same volume of cake.
Problem is, there is another person, $C$, who has already split the cake into a finite number of pieces, each piece being of a volume which is a negative power of two: of the form $\dfrac{1}{2^k}$ for some integer $k \gt 0$. The pieces need not have the same volume and you could have multiple pieces with the same volume. For example, one such split could be $\{\frac{1}{8}, \frac{1}{8}, \frac{1}{4}, \frac{1}{2}\}$.
$C$ is also holding the cake hostage, and will only give you one piece at a time (in some random order), on the condition that you immediately make a decision who ($A$ or $B$) to give the piece to. You cannot revisit that piece later.
Can you think of an algorithm which will help split the cake equally between $A$ and $B$ in this scenario? Just an algorithm won't do, you need to prove that it works too.
[For the reason why it is called online, read this]
[Solution]
Problem is, there is another person, $C$, who has already split the cake into a finite number of pieces, each piece being of a volume which is a negative power of two: of the form $\dfrac{1}{2^k}$ for some integer $k \gt 0$. The pieces need not have the same volume and you could have multiple pieces with the same volume. For example, one such split could be $\{\frac{1}{8}, \frac{1}{8}, \frac{1}{4}, \frac{1}{2}\}$.
$C$ is also holding the cake hostage, and will only give you one piece at a time (in some random order), on the condition that you immediately make a decision who ($A$ or $B$) to give the piece to. You cannot revisit that piece later.
Can you think of an algorithm which will help split the cake equally between $A$ and $B$ in this scenario? Just an algorithm won't do, you need to prove that it works too.
[For the reason why it is called online, read this]
[Solution]
No comments:
Post a Comment