An averaging game on finite multisets of integers

Question

The following procedure is a variant of one suggested by Patrek Ragnarsson (age 10). Let $M$ be a finite multiset of integers. A move consists of choosing two elements $a\neq b$ of $M$ of the same parity and replacing them with the pair $\frac 12(a+b)$, $\frac 12(a+b)$. If we continue to make moves whenever possible, the procedure must eventually terminate since the sum of the squares of the elements will decrease at each move. What is the least and the most number of moves to termination, in particular, if $M=\{1,2,\dots, n\}$? If $M=\{a_1,\dots,a_n\}$, then an upper bound on on the maximum number of moves is $\frac 12\sum (a_i-k)^2$, where $k$ is the integer which minimizes this sum. (In fact, $k$ is the nearest integer to $\frac 1n(a_1+\cdots+a_n)$.)

We can turn this procedure into a game by having Alice and Bob move alternately, with Alice moving first. The last player to move wins. (We could also consider the misère version, where the last player to move loses.) Which multisets are winning for Alice, especially $M=\{1,2,\dots,n\}$? The game is impartial, so it has a Sprague-Grundy number. However, it doesn't seem to be useful for analyzing the game since a position $M$ never breaks up into a disjoint union (or sum) of smaller independent positions. Nevertheless we can ask for the Sprague-Grundy number of a position $M$.

Answer 1

This doesn't address the whole question, but symmetry considerations show that when $M = \{1,2,\ldots, 2m\}$, the second player has a winning strategy. Details are below...

Let's say that a multiset $M$ is symmetric about $c$ if the multiplicity of an element $x$ in $M$ is equal to the multiplicity of $2c-x$. By taking the sum of the elements, we see that $M$ can be symmetric about at most one element $c$; $c$ is forced to be the arithmetic mean of $M$. During the game, $M$ may cease to be symmetric, or may become symmetric, but the point of symmetry is determined. (Since $M$ consists of integers, such a $c$ would be forced to be in $\frac{1}{2}\mathbb{Z}$, so this doesn't happen for most multisets of integers.)

In the case where $M = \{1,2,\ldots, 2m\}$, $M$ is symmetric about $c=m+\frac{1}{2}$. Consider the following strategy for the second player, Bob. In the previous turn, Alice chose two numbers $a_1, a_2$ of the same parity. Bob chooses $b_1 = 2c-a_1, b_2 = 2c-a_2$. If $M$ was symmetric before Alice's turn, then the fact that $a_1, a_2 \in M$ implies $b_1, b_2 \in M$. Bob's move is then guaranteed to be valid because $b_1, b_2$ have the same parity, which is different to the parity of the elements $a_1, a_2$ chosen by Alice (so Alice cannot have removed either of $b_1, b_2$ prior to Bob's turn, because $a_1, a_2$ have different parity). Moreover, it is also easy to see that Bob's move returns $M$ to a state that is symmetric about $c$. So Bob will always be able to play, and therefore will win.

This argument doesn't extend to the odd case. Suppose $M = \{1,2,3,4,5\}$. Alice could remove $1, 3$, and the symmetric entries, $3$ and $5$, are not a valid move for Bob. Alternatively, Alice could remove $2, 4$ which gives Bob a symmetric board state.