I accepted this answer although it is not complete. I really like the way you are applying elementary methods to this problem. As a side note, I am not sure one can easily tell the difference between $n^{3/2}$ and $n^{4/3} \log{n}$ empirically so the latter could well turn out to be the right answer.

That is correct.

I am sorry this may be hopelessly naive, but how does one typically establish that there is a scaling law without determining what it is?

@ButchMalahide Do you know a reference for that remarkable fact?

As this is computer science, they probably want an asymptotic answer rather than for fixed $n$. Is it asymptotically $n^{3/4}$?

An exact asymptotic answer for rule 1 of $2^{n-1}$ sounds perfect. I wonder if rule 2 has an attractive asymptotic answer too.

Also asked here I see gilkalai.wordpress.com/2013/04/27/taking-balls-away-oz-versi‌​on with a promised answer "soon".

I have also seen this puzzle and was told the answer is $n^{3/4}$ on average. I don't know how to solve it.