Online number partitioning
A simple yet surprisingly interesting result.
You have a bunch of numbers each in the form of \(2^{-k}\) where \(k>0\), and they sum up to \(1\). You want to partition them into two groups of equal sum, i.e. each group sums up to \(1/2\). It has to be done online: for each number you have to decide which group to throw into, and are not allowed to revisit it again. How?
Solution:
For each number, if adding it to group \(A\) doesn't make it exceed \(1/2\), then do it. Otherwise add it to group \(B\). It'll just work. Correctness is not hard to prove.
You have a bunch of numbers each in the form of \(2^{-k}\) where \(k>0\), and they sum up to \(1\). You want to partition them into two groups of equal sum, i.e. each group sums up to \(1/2\). It has to be done online: for each number you have to decide which group to throw into, and are not allowed to revisit it again. How?
Solution:
For each number, if adding it to group \(A\) doesn't make it exceed \(1/2\), then do it. Otherwise add it to group \(B\). It'll just work. Correctness is not hard to prove.
post by Shen-Fu Tsai