Skip to main content
MathOverflow

Return to Answer

Bounty Awarded with 150 reputation awarded by Noah Schweber
added 1060 characters in body
Source Link
paste bee
paste bee
  • 2.8k
  • 11
  • 16

This is still a heavily computer-assisted argument, and also really long and annoying, but I think I have a complete proof that strange positions don't exist. I'm going to use the same notation as Mikhail's answer. Also, the "value" of a position is the set of 2$2$-player coalitions for which that position is winning, just because that concept is annoyingly long to express otherwise.

Property 2 of the above list holds for all $a$, by a simple inductive argument, using the computer validation for $a \leq 15$ as the base case: any move from a position $1^{a+5}2^b3^c4^d5^e$ has a corresponding move from the position $1^a2^b3^c4^d5^e$ to the same position except with 5$5$ less piles of size 1$1$, which by the induction hypothesis has the same value; and so it has the same value as well, because the value of a position is determined by the values of each position that it can move to.

Property 3, combined with the above result extending it to all values of $a$, implies that any position with all stacks of height at most 5$5$ outside the range my code checked is not winning for any 2$2$-player coalition: play in such a position must eventually reach one of the "edges" of the range, which are all covered by property 3, and no 2$2$-player coalition can have a winning strategy once that happens. (This could also be framed as another inductive argument, but I find this approach easier).

A similar argument, combined with property 4, establishes the same thing for positions with one stack of height 6$6$ and otherwise all stacks of height at most 5$5$: either the stack of height 6$6$ is reduced, leaving the position in a situation covered by the above paragraph, or that never happens and it hits one of the edges (although note that in this case the edge is $e = 2$ rather than $e = 3$).

  • Reduce all stacks of size $> 5$ to stacks of size $5$.
  • Repeatedly subtract 5 fromremove $a$$5$ stacks of size $1$, until there are at most $a < 7$$6$.
  • If there are (at least) 10$10$ stacks of size 2$2$, or 6$6$ stacks of size 3$3$, or 3$3$ stacks of size 4$4$, or 3$3$ stacks of size 5$5$, the position is not winning.
  • This leaves only finitely many cases.

For a set $S$ of two-player coalitions, here is a game in which $S$ is exactly the set of two-player winning coalitions. Each player declares the coalition that they are part of, which must be either an element of $S$, or a three-element set whose complement is not in $S$. The first player who is not in a valid coalition (meaning everyone in the coalition they selected also selected that coalition) loses. This is a generalisation of the construction in my comment, and demonstrates that all $1024$ possible sets of $2$-player coalitions are possible values for $5$-player games.

Only $55$ of these $1024$ values occur in $5$-player Nim. This is a pretty small number, so it seems plausible that in some sense the nonexistence of a strange position in particular is just a lack of an odd coincidence, rather than anything with a particularly deep explanation.

This is still a heavily computer-assisted argument, and also really long and annoying, but I think I have a complete proof that strange positions don't exist. I'm going to use the same notation as Mikhail's answer. Also, the "value" of a position is the set of 2-player coalitions for which that position is winning, just because that concept is annoyingly long to express otherwise.

Property 2 of the above list holds for all $a$, by a simple inductive argument, using the computer validation for $a \leq 15$ as the base case: any move from a position $1^{a+5}2^b3^c4^d5^e$ has a corresponding move from the position $1^a2^b3^c4^d5^e$ to the same position except with 5 less piles of size 1, which by the induction hypothesis has the same value; and so it has the same value as well, because the value of a position is determined by the values of each position that it can move to.

Property 3, combined with the above result extending it to all values of $a$, implies that any position with all stacks of height at most 5 outside the range my code checked is not winning for any 2-player coalition: play in such a position must eventually reach one of the "edges" of the range, which are all covered by property 3, and no 2-player coalition can have a winning strategy once that happens. (This could also be framed as another inductive argument, but I find this approach easier).

A similar argument, combined with property 4, establishes the same thing for positions with one stack of height 6 and otherwise all stacks of height at most 5: either the stack of height 6 is reduced, leaving the position in a situation covered by the above paragraph, or that never happens and it hits one of the edges (although note that in this case the edge is $e = 2$ rather than $e = 3$).

  • Reduce all stacks of size $> 5$ to stacks of size $5$.
  • Repeatedly subtract 5 from $a$ until $a < 7$.
  • If there are (at least) 10 stacks of size 2, or 6 stacks of size 3, or 3 stacks of size 4, or 3 stacks of size 5, the position is not winning.
  • This leaves only finitely many cases.

This is still a heavily computer-assisted argument, and also really long and annoying, but I think I have a complete proof that strange positions don't exist. I'm going to use the same notation as Mikhail's answer. Also, the "value" of a position is the set of $2$-player coalitions for which that position is winning, just because that concept is annoyingly long to express otherwise.

Property 2 of the above list holds for all $a$, by a simple inductive argument, using the computer validation for $a \leq 15$ as the base case: any move from a position $1^{a+5}2^b3^c4^d5^e$ has a corresponding move from the position $1^a2^b3^c4^d5^e$ to the same position except with $5$ less piles of size $1$, which by the induction hypothesis has the same value; and so it has the same value as well, because the value of a position is determined by the values of each position that it can move to.

Property 3, combined with the above result extending it to all values of $a$, implies that any position with all stacks of height at most $5$ outside the range my code checked is not winning for any $2$-player coalition: play in such a position must eventually reach one of the "edges" of the range, which are all covered by property 3, and no $2$-player coalition can have a winning strategy once that happens. (This could also be framed as another inductive argument, but I find this approach easier).

A similar argument, combined with property 4, establishes the same thing for positions with one stack of height $6$ and otherwise all stacks of height at most $5$: either the stack of height $6$ is reduced, leaving the position in a situation covered by the above paragraph, or that never happens and it hits one of the edges (although note that in this case the edge is $e = 2$ rather than $e = 3$).

  • Reduce all stacks of size $> 5$ to stacks of size $5$.
  • Repeatedly remove $5$ stacks of size $1$, until there are at most $6$.
  • If there are (at least) $10$ stacks of size $2$, or $6$ stacks of size $3$, or $3$ stacks of size $4$, or $3$ stacks of size $5$, the position is not winning.
  • This leaves only finitely many cases.

For a set $S$ of two-player coalitions, here is a game in which $S$ is exactly the set of two-player winning coalitions. Each player declares the coalition that they are part of, which must be either an element of $S$, or a three-element set whose complement is not in $S$. The first player who is not in a valid coalition (meaning everyone in the coalition they selected also selected that coalition) loses. This is a generalisation of the construction in my comment, and demonstrates that all $1024$ possible sets of $2$-player coalitions are possible values for $5$-player games.

Only $55$ of these $1024$ values occur in $5$-player Nim. This is a pretty small number, so it seems plausible that in some sense the nonexistence of a strange position in particular is just a lack of an odd coincidence, rather than anything with a particularly deep explanation.

Source Link
paste bee
paste bee
  • 2.8k
  • 11
  • 16

This is still a heavily computer-assisted argument, and also really long and annoying, but I think I have a complete proof that strange positions don't exist. I'm going to use the same notation as Mikhail's answer. Also, the "value" of a position is the set of 2-player coalitions for which that position is winning, just because that concept is annoyingly long to express otherwise.

This Rust code checks the following properties for positions of the form $1^a2^b3^c4^d5^e$ with $(a,b,c,d,e) \leq (20,10,6,3,3)$:

  1. None of them are strange.
  2. If $2 \leq a \leq 15$, then the position has the same value as $1^{a+5}2^b3^c4^d5^e$. (It isn't particularly necessary to check this property until 15, but I didn't want to work out exactly how far was necessary and risk getting it wrong; the program only takes a few seconds to run, so it's not that important).
  3. If $b = 10$, or $c = 6$, or $d = 3$, or $e = 3$, the position is not winning for any 2-player coalition.
  4. If $e \geq 1$, it has the same value as $1^a2^b3^c4^d5^{e-1}6$.

Property 2 of the above list holds for all $a$, by a simple inductive argument, using the computer validation for $a \leq 15$ as the base case: any move from a position $1^{a+5}2^b3^c4^d5^e$ has a corresponding move from the position $1^a2^b3^c4^d5^e$ to the same position except with 5 less piles of size 1, which by the induction hypothesis has the same value; and so it has the same value as well, because the value of a position is determined by the values of each position that it can move to.

Property 3, combined with the above result extending it to all values of $a$, implies that any position with all stacks of height at most 5 outside the range my code checked is not winning for any 2-player coalition: play in such a position must eventually reach one of the "edges" of the range, which are all covered by property 3, and no 2-player coalition can have a winning strategy once that happens. (This could also be framed as another inductive argument, but I find this approach easier).

A similar argument, combined with property 4, establishes the same thing for positions with one stack of height 6 and otherwise all stacks of height at most 5: either the stack of height 6 is reduced, leaving the position in a situation covered by the above paragraph, or that never happens and it hits one of the edges (although note that in this case the edge is $e = 2$ rather than $e = 3$).

Now we extend this further: all positions with stacks of heights $> 5$ have the same value as the position where all of these stacks are reduced to 5, by induction. Call the position $P$, and the reduced position $Q$. By the induction hypothesis, each move from $P$ has the same value as the corresponding move from $Q$, so the only difference is that moves in $P$ like "reduce a stack of size $6$ to size $5$", which (by the induction hypothesis) lead to positions with the same value as $Q$, have been removed. But this means it has exactly the same set of move values as the position obtained by increasing one of the $5$s in $Q$ to a $6$, which by the previous paragraph has the same value as $Q$. So $P$ and $Q$ have the same value.

To summarize, here is a "complete" description of how to compute if a position is winning:

  • Reduce all stacks of size $> 5$ to stacks of size $5$.
  • Repeatedly subtract 5 from $a$ until $a < 7$.
  • If there are (at least) 10 stacks of size 2, or 6 stacks of size 3, or 3 stacks of size 4, or 3 stacks of size 5, the position is not winning.
  • This leaves only finitely many cases.