# 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.