How Does Choosing Ball Subsets Affect Their Weight Growth in an Algorithm?

[OfirD]

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 1+\frac{1}{|S|} 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 \phi 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.

 

[Privalov]

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 1+\frac{1}{|S|} 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.

Let’s take n=6 for example. Am I allowed to make O(n log(n)) = 4.66 turns in the game? Should I round it up to 4 or 5?

this is easy to show for example, if the subsets are always of size 1, or of size n.

Again, let’s take n=6 for example.
If the subsets are always of size 1, game will have 6 iterations
If the subsets are always of size n, game will have 5 iterations
Both numbers are larger than 4.66, what is, as far as I understand, the predicted number of turns.

Big O notation assumes n approaches infinity and any coefficients should be omitted. Is it the case in your problem? I will assume this is the case; otherwise problem description does not make too much cense.

Let’s look at the following strategy.
Step 1. Opponent chooses balls 1 and 2.
Step 2. Balls 3 and 4.
Step 3. Balls 5 and 6.
Etcetera: two balls per step, until they run out.
Then, opponent starts over and chooses balls 1,2,3,… again – one ball at a time.

Please see this spreadsheet for demonstration of this algorithm for n=8.

http://ganymed.ca/temp/Upper_bound_problm_8.xls

As you can see, the number of steps is 12. The run time of this algorithm is O(1.5 * n), what is equal to O(n). So, your upper boundary looks correct.

I will have to think about your problem.

By the way, in my chart, yellow fields are for user input; white fields are calculated. Field B1 is for number n. Chart of yellow fields should be filled of 1’s and blanks. 1 will indicate ball is selected in this step. White numbers below are the weights of the balls. Each column corresponds to one ball; row corresponds to one iteration.

 

[Privalov]

I assume |S| in your formula is total weight of selected balls, not the count of selected balls, correct?

 

[OfirD]

Thanks, but I already found a solution. the potential function should be the multiplication of the weights and not their sum.
any way, the big O notation means that there is a constant C and and a natural number N, such that for all n>N , C n log(n) is an upper bound

 

[Privalov]

Thanks, but I already found a solution.

Me too.
Maximum number of game iterations is 2*n-2, correct?
So, complexity is O(n).