11
$\begingroup$

What are some examples of mathematical games that can take an unbounded amount of time (a.k.a. there are starting positions such that for any number $n$, there is a line of play taking $>n$ times) but is finite (every line of play eventually ends.) Also, it would be nice if it were recreational in nature (by this I mean I basically mean its nontrivial, I could conceivably be enjoyed by humans theortically.) One answer per game please, but edit variants into the same answer.

This is a big-list question, so many answers would be appreciated.

$\endgroup$
  • 2
    $\begingroup$ Well, there's always the ring game, though maybe that requires certain friends. $\endgroup$ – Milo Brandt Mar 27 '15 at 0:59
  • $\begingroup$ @Meelo That's worth an answer (by recreational, I mostly mean nontrivial.) $\endgroup$ – PyRulez Mar 27 '15 at 1:09
  • $\begingroup$ Did you mean a line of play taking $\gt n$ times? $\endgroup$ – Ross Millikan Mar 27 '15 at 1:16
  • $\begingroup$ Nim certainly qualifies, but I am not sure it counts as recreational. $\endgroup$ – Ross Millikan Mar 27 '15 at 1:17
  • $\begingroup$ @RossMillikan Infinite nim with a large but finite number of heaps would be fun. $\endgroup$ – PyRulez Mar 27 '15 at 1:29
7
$\begingroup$

One example is Sylver's Coinage played like so:

Player's alternate selecting positive integers ($1, 2, 3, 4\dots$). The rule is that no number is allowed to be expressed as sum (with possible duplicates) of the previous. For example, say $\{4, 8, 5, 7\}$ ($8$ would have had to been said before $4$) was previously said. Then $6$ could be said, but $14$ could not, for it is equal to $5+5+4$ (or $7+7$.) The player who says $1$ loses! (If you prefer normal play convention, outlaw the number $1$ and then the last player who can move wins!)

This game is unbounded ($\{n, n-1, n-2, \dots n/2\}$), but, according to a theorem of arithmetic, finite (if you have trouble even seeing how this game could end, note that when $2$ and $3$ are said, all even numbers, and all odd number more that $3$ are illegal.

Does anyone know any variants (say based on different mathematical structures than positive integers? Ordinals maybe?)

$\endgroup$
  • $\begingroup$ You can probably play on the polynomials in $X_1,\dots X_k$ with non-negative integer coefficients. (Because of Hilbert's Basis Theorem?) $\endgroup$ – Oscar Cunningham Mar 27 '15 at 8:35
5
$\begingroup$

One example is the ring game, which is defined here - in essence, the game (or a slight variant thereon) can be described as:

Start with a Noetherian ring $R$. At each turn, replace $R$ with a quotient thereof. If a player can make no legal moves (i.e. $R$ is a field, thus has no proper quotients).

One can notice that if we play this on $\mathbb Z$, then this is equivalent to the game $*\omega$, since the first move takes it to $\mathbb Z/n\mathbb Z$ which is clearly equivalent to $*k$ where $k$ is the number of (not necessarily distinct) prime factors of $n$. However, as evidenced by certain unanswered questions, the structure of the game can get fairly complicated when we consider more complicated rings. One could generalize to replace "ring" with any algebraic structure they desire - like one could play on groups with no infinite ascending chains of normal subgroups.

$\endgroup$
  • $\begingroup$ "One could generalize to replace "ring" with any algebraic structure they desire" In particular taking $\mathbb{N}$ gives Sylver coinage and taking the free monoid on some generators gives Higman's game; the two other examples posted so far! $\endgroup$ – Oscar Cunningham Mar 27 '15 at 8:39
  • $\begingroup$ Taking the algebraic structure to be "well founded relations" and the operation to be "quotient out a filter" gives a class of games containing Nim. $\endgroup$ – Oscar Cunningham Mar 27 '15 at 8:44
4
$\begingroup$

Higman's game$^*$

Using finite words on a fixed finite alphabet, two players take turns, in each turn specifying a word that contains no already-specified word as a subsequence. The game terminates when a player (declared the loser) is unable to specify a word, and the other player is declared the winner.

By Higman's Lemma, every such game must eventually terminate; nevertheless, the playing time is arbitrarily large, depending on the initial words chosen.

$^*$ I'm making up the name and the game. Similar games with much longer finite potential playing times could involve specifying trees or graphs (instead of words) that avoid homeopmorphic embeddings, and appealing to Kruskal's Tree Theorem or to the Robertson-Seymour Theorem for proof of termination. These are all examples of the following generalization:

WQO games

More generally, suppose $(X,\le)$ is any well-quasi-order (WQO). Now if players take turns specifying elements of $X$, then eventually one of the players cannot avoid specifying an element $x_j$ such that $x_i\le x_j$ for some already-specified element $x_i$ (i.e., $i<j$), thus terminating the game. The playing time is always finite but arbitrarily large, depending on the initially-chosen elements.

$\endgroup$
  • $\begingroup$ The name is good given the name of sylver coinage. $\endgroup$ – PyRulez Mar 28 '15 at 3:44
  • $\begingroup$ The graph game might be interesting. $\endgroup$ – PyRulez Oct 28 '17 at 4:55
  • $\begingroup$ Oh, and the well-quasi-order on $\mathbb{N} \times \mathbb{N}$ given by Dickson's lemma would correspond to $\omega \times \omega$ Chomp. $\endgroup$ – PyRulez Oct 28 '17 at 6:03
2
$\begingroup$

The Hydra problem can be converted in a game with several players. The first player chooses the hydra. Players take turns cutting heads.

$\endgroup$
0
$\begingroup$

Entrepreneurial Chess (Echess). A game of Echess position begins with a Black king vs. a White king and a White rook on a quarter-infinite board, spanning the first quadrant of the xy-plane. In addition to the normal chess moves, Black is given the additional option of “cashing out”, which removes the board and converts the position into the integer x+y, where [x, y] are the coordinates of his king’s position when he decides to cash out.

For each starting position, the game would only last for a finite number of times if both sides play perfectly. In fact white will always win if black does not cash out. But as the starting positions vary, the play time can become arbitrarily long.

References to Echess if you want to know more:

$\endgroup$

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.