## vector game

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

### vector game

Let |v| denote the sum of components of v.
Consider the following game.
The game state is a vector M in R^n, and is initialized as the 0 vector.
A valid move is a vector v in R^n such |v| = 1 and v >= 0
The game state after move v is s(M+v), where s(x) subtracts 1 from the largest component in x.
The score of a game state is the largest component in M.
What is the finite sequence of moves, V = v1, v2, .... vk which will maximize the score. What is the maximum possible score?

So far, I have found an upper bound of n and a lower bound of O(log n)

Spoiler:
Notice that |M| = 0 at every turn.
Notice that |M+v| = 1 at every turn, so at least one component of M+v is positive.
Therefore, s(x) subtracts only from a positive component, so M > -1 is always true.
The absolute value of the sum of the negative components of M is therefore less than n
The sum of the absolute values of negative components of M is the sum of the positive components of M since |M| = 0.
So the sum of the positive components of M' is therefore less than n.
Therefore the largest component of M is less than n.

Spoiler:
Consider
v1 = [1/n, 1/n, ..... 1/n]
v2 = [1/(n-1), 1/(n-1), .... 1/(n-1), 0]
v3 = [1/(n-2), 1/(n-2), .... 1/(n-2), 0, 0]
.
.
.
vn-1 = [1/2, 1/2, 0, .... 0]
vn = [1, 0, .... 0]
and assume for convenience that s always subtracts 1 from the last of the largest components if there is a tie.
Then notice that the first component of M sums to O(log n) after all n moves are made.
I conjecture that this is the maximum score which can be achieved. However, I cannot prove this.