- #1
OfirD
- 3
- 0
there are n balls of weight 1/n.
an opponent choose each time a subset of balls that each one has weight less than 1. then each ball in this set, its weight is multiplied by [tex]1+\frac{1}{|S|}[/tex] where S is the set of balls that the opponent chose.
I need to show that for each choice of subsets, after O(n log(n)), all the balls have weights greater than one.
this is easy to show for example, if the subsets are always of size 1, or of size n. also there is no real importance to the order of the choices of the subsets, because eventually this is just multiplication of the weight values, and so this is commutative.
I tried to show this by defining the function [tex]\phi[/tex] which is the average of the weights, and see how it is increased in each iteration, but didn't get very far.
another way I thought of is to show, that if I order the sets so that each time I choose the set that the average of its elements is the smallest, then after n iterations, each elements is multiplied by 2. this is true for the choices of always n balls, and of always 1 ball.
an opponent choose each time a subset of balls that each one has weight less than 1. then each ball in this set, its weight is multiplied by [tex]1+\frac{1}{|S|}[/tex] where S is the set of balls that the opponent chose.
I need to show that for each choice of subsets, after O(n log(n)), all the balls have weights greater than one.
this is easy to show for example, if the subsets are always of size 1, or of size n. also there is no real importance to the order of the choices of the subsets, because eventually this is just multiplication of the weight values, and so this is commutative.
I tried to show this by defining the function [tex]\phi[/tex] which is the average of the weights, and see how it is increased in each iteration, but didn't get very far.
another way I thought of is to show, that if I order the sets so that each time I choose the set that the average of its elements is the smallest, then after n iterations, each elements is multiplied by 2. this is true for the choices of always n balls, and of always 1 ball.