An averaging game on finite multisets of integers 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$.
 A: 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.
