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?

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