9
$\begingroup$

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$.

$\endgroup$
7
  • 2
    $\begingroup$ You probably want to force $a\neq b$? or else one in most case, at some point, choose a pair of equal numbers to increase artificially the number of moves. So termination is when all numbers in $M$ of the same parity are equal. $\endgroup$
    – YCor
    Oct 3 '20 at 0:14
  • 1
    $\begingroup$ Have you gone through the experiment and pattern spotting procedures? $\endgroup$
    – WhatsUp
    Oct 3 '20 at 0:56
  • 2
    $\begingroup$ If $n=2m+1$ is odd you can clearly terminate starting from $\{1,2,\ldots,n\}$ in $m$ steps by choosing the $a,b$ with $a+b=n+1$. $\endgroup$ Oct 3 '20 at 1:07
  • 2
    $\begingroup$ For $n\le 8$ here's the set of possible stopping times starting from $\{1,\dots,n\}$. For $n=8$ it starts taking some time. $n\le 2$: $[0]$; $n=3$: $[1]$; $n=4$: $[2]$; $n=5$: $[2,5]$; $n=6$: $[2,5,8]$; $n=7$: $[3,5,6,8,11,14]$; $n=8$: $[4,6,8,9,11,12,14,17,20]$. $\endgroup$
    – YCor
    Oct 3 '20 at 7:37
  • 1
    $\begingroup$ For $n=9$ by random walk on the graph I obtain the following stopping times (I don't claim these are the only possible ones). I checked once by choosing random $(a,b)$ among possibles, and once by choosing random $(a,b)$ among possible minimizing $b-a$. Did 30000 tests in each case. (Choosing random $(a,b)$ among possible maximizing $b-a$, in all 20000 tests, yields stopping time 4.) The obtained times: $[4,6,\dots,16,18,19,21,22,24,27,30]$. (With the minimizing $b-a$ option, I obtained stopping time 6 with probability about $1/12$, and the most likely is stopping time $24$: almost $1/2$.) $\endgroup$
    – YCor
    Oct 3 '20 at 9:10
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ what if $b_2=a_1$? $\endgroup$ Oct 4 '20 at 23:57
  • $\begingroup$ A valid move requires $a_1$ and $a_2$ to have the same parity, and similarly $b_1$ and $b_2$ to have the same parity (otherwise their average is not an integer). So if $b_2 = a_1$, then all four numbers have the same parity, contradicting the definition of the $b_i$. $\endgroup$ Oct 5 '20 at 1:30
  • $\begingroup$ Indeed, thank you. $\endgroup$ Oct 5 '20 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.