 | This article may be too technical for most readers to understand.(October 2018) |
Sprouts is an impartial paper-and-pencil game which can be analyzed for its mathematical properties. It was invented by mathematicians John Horton Conway and Michael S. Paterson [1] at Cambridge University in the early 1960s. The setup is even simpler than the popular Dots and Boxes game, but gameplay develops much more artistically and organically.
The game is played by two players, [2] starting with a few spots drawn on a sheet of paper. Players take turns, where each turn consists of drawing a line between two spots (or from a spot to itself) and adding a new spot somewhere along the line. The players are constrained by the following rules:
In so-called normal play, the player who makes the last move wins. In misère play , the player who makes the last move loses. Misère Sprouts is perhaps the only misère combinatorial game that is played competitively in an organized forum. [3]
The diagram on the right shows a 2-spot game of normal-play Sprouts. After the fourth move, most of the spots are dead–they have three lines attached to them, so they cannot be used as endpoints for a new line. There are two spots (shown in green) that are still alive, having fewer than three lines attached. However, it is impossible to make another move, because a line from a live spot to itself would make four attachments, and a line from one live spot to the other would cross lines. Therefore, no fifth move is possible, and the first player loses. Live spots at the end of the game are called survivors and play a key role in the analysis of Sprouts.
The game of Sprouts always terminates, although this fact is not evident from the game rules, since the number of spots increases at each move. The approach to understand why the game always terminates is to consider the number of lives (opportunities to connect a line) instead of the number of spots. Then, it can be shown that if the game starts with n spots, it will end in no more than 3n − 1 moves and no fewer than 2n moves.
In the following proofs, it is assumed that a game starts with n spots and lasts for exactly m moves.
Each spot starts with three lives and each move reduces the total number of lives in the game by one (two lives are lost at the ends of the line, but the new spot has one life). So at the end of the game there are 3n − m remaining lives. Each surviving spot has only one life (otherwise there would be another move joining that spot to itself), so there are exactly 3n − m survivors. There must be at least one survivor, namely the spot added in the final move. So 3n − m ≥ 1; hence a game can last no more than 3n − 1 moves.
This upper bound is actually the maximum, and it can be attained in many ways by ensuring that there is only one survivor at the end of the game. For instance, the game on the right has one survivor and 3n − 1 moves.
At the end of the game, a dead spot is called the neighbor of a survivor if it is either adjacent to that survivor or, if the survivor has a loop, it is adjacent to a spot adjacent to the survivor. This is illustrated in the diagram to the right. Each survivor has exactly two dead neighbors. No dead spot can be the neighbor of two different survivors, for otherwise there would be a move joining the survivors. All other dead spots (not neighbors of a survivor) are called pharisees (from the Hebrew for "separated ones"). Suppose there are p pharisees. Then
since initial spots + moves = total spots at end of game = survivors + neighbors + pharisees. Rearranging gives:
Consequently, a game lasts for at least 2n moves, and the number of pharisees is divisible by 4.
This lower bound on the length of a game is actually the minimum. The diagram on the right shows a completed game of 2n moves. It has n survivors, 2n neighbors and 0 pharisees.
Real games seem to turn into a battle over whether the number of moves will be k or k + 1 with other possibilities being quite unlikely. [4] One player tries to create enclosed regions containing survivors (thus reducing the total number of moves that will be played) and the other tries to create pharisees (thus increasing the number of moves that will be played).
Since Sprouts is a finite game where no draw is possible, a perfect strategy exists either for the first or the second player, depending on the number of initial spots. The main question about a given starting position is then to determine which player can force a win if they play perfectly.
When the winning strategy is for the first player, it is said that the outcome of the position is a "win", and when the winning strategy is for the second player, it is said that the outcome of the position is a "loss" (because it is a loss from the point of view of the first player).
The outcome is determined by developing the game tree of the starting position. This can be done by hand only for a small number of spots, and all the new results since 1990 have been obtained by extensive search with computers.
Winning Ways for your Mathematical Plays reports that the 6-spot normal game was proved to be a win for the second player by Denis Mollison, with a hand-made analysis of 47 pages. It stood as the record for a long time, until the first computer analysis, which was done at Carnegie Mellon University in 1990 by David Applegate, Guy Jacobson, and Daniel Sleator. [5] They reached up to 11 spots with some of the best hardware available at the time.
Applegate, Jacobson and Sleator observed a pattern in their results, and conjectured that the first player has a winning strategy when the number of spots divided by six leaves a remainder of three, four, or five. This is a mathematical way of saying that the pattern displayed by the outcome in the table below repeats itself indefinitely, with a period of six spots.
| Spots | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | ... |
| Normal Outcome | Loss | Loss | Loss | Win | Win | Win | Loss | Loss | Loss | Win | Win | Win | ... |
In 2001, Riccardo Focardi and Flamina Luccio described a method to prove by hand that the normal 7-spot game is a loss. [6]
Then, the computation results were extended in 2006 by Josh Jordan up to 14 spots. In 2007, Julien Lemoine and Simon Viennot introduced an algorithm based on the concept of nimbers to accelerate the computation, reaching up to 32 spots. [7] They have extended the computation up to 44 spots in 2011, and three isolated starting positions, with 46, 47 and 53 spots. [8]
The normal-play results so far are all consistent with the conjecture of Applegate, Jacobson, and Sleator.
The computation history of the misère version of Sprouts is very similar to that of the normal version, with the same people involved. However, the misère version is more difficult to compute, and progress has been significantly slower.
In 1990, Applegate, Jacobson and Sleator reached up to nine spots. Based on their results, they conjectured that the outcome follows a regular pattern of period five. However, this conjecture was invalidated in 2007 when Josh Jordan and Roman Khorkov extended the misère analysis up to 12 spots: the 12-spot misère game is a win, and not the conjectured loss. The same team reached up to 16 spots in 2009. [9] The same year, Julien Lemoine and Simon Viennot reached 17 spots with complicated algorithms. [10] They were able to extend their analysis up to 20 points in 2011. [8]
The results for misère play are now conjectured to follow a pattern of length six with some exceptional values: the first player wins in misère Sprouts when the remainder (mod 6) is zero, four, or five, except that the first player wins the one-spot game and loses the four-spot game. The table below shows the pattern, with the two irregular values in bold.
| Spots | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ... |
| Misère Outcome | Win | Win | Loss | Loss | Loss | Win | Win | Loss | Loss | Loss | Win | Win | Win | Loss | Loss | Loss | ... |
A variant of the game, named Brussels Sprouts after the cruciferous vegetable, starts with a number of crosses, i.e. spots with four free ends. Each move involves joining two free ends with a curve, again not crossing any existing line, and then putting a short stroke across the line to create two new free ends. This game is finite, and the total number of moves (and thus the game's winner) is predetermined by the initial number of crosses: the players cannot affect the result by their play. Thus, this variant may be termed, after Conway's categorisation of mathematics itself, a "one player game".
Each move removes two free ends and introduces two more. Nonetheless, the game is bound to end as some free ends become isolated. With n initial crosses, the number of moves will, remarkably, always be 5n − 2. Consequently, a game starting with an odd number of crosses will be a first player win, while a game starting with an even number will be a second player win regardless of the moves.
To prove this, first, we argue the game must end. Then, we will calculate precisely how many moves it needs to end. The game outcome is then implied, as already described.
Treat each cross as a graph with 5 vertices and 4 edges. In the starting position with n crosses, we have a planar graph with v = 5n vertices, e = 4n edges, f = 1 face, and k = n connected components. The Euler characteristic for connected planar graphs is 2. In a disconnected planar graph, we get
After m moves, we have:
Then by the above, we have
Next, note that every time we add a cross, we are ensuring that each side of this cross ends up with a degree 1 vertex. Thus, throughout the game, every face has at least one degree 1 vertex. Yet, the number of degree 1 vertices is invariant throughout the game, and remains at 4n. Hence, f is at most 4n.
From this, we see m = f − k − 1 + n is at most 5n − 2 (since k is at least 1 and f is at most 4n). So the game must terminate, and it must terminate in at most 5n − 2 moves. Now, we argue it must terminate in exactly 5n − 2 moves.
In the final configuration, no face can have more than one degree 1 vertex, since otherwise, we could connect them with a cross and there would still be a legal move. Every face has at least one such vertex, so it must end with exactly one such vertex. So in the final configuration, f is exactly 4n.
Similarly, in the final configuration, the graph must be connected, since the outer face gets at least one degree 1 vertex per connected component, and cannot have more than one such vertex. So, in the final configuration, k is exactly 1.
Thus, to obtain the final configuration, we must have had m = f−k−1+n = 4n−1−1+n = 5n−2.
A combination of standard Sprouts and Brussels Sprouts can also be played. The game starts with an arbitrary number (n) of dots or crosses. At each turn, the player chooses to add either a dot, or a cross, along the line they have just drawn. The duration of the game lays between (2n) and (5n − 2), depending on the number of dots or crosses having been added.
For n = 1, starting with a dot, the game will end after 2 moves. Starting with a cross, it will end after 2 moves if the first player adds a dot, after 3 moves if they add a cross: hence the first player has a winning strategy for both the normal and the misère version. For n > 1, the analysis is not completed.
The Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1. It concerns sequences of integers in which each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence.
In number theory, Bertrand's postulate is the theorem that for any integer , there exists at least one prime number with
In geometry, a prism is a polyhedron comprising an n-sided polygon base, a second base which is a translated copy of the first, and n other faces, necessarily all parallelograms, joining corresponding sides of the two bases. All cross-sections parallel to the bases are translations of the bases. Prisms are named after their bases, e.g. a prism with a pentagonal base is called a pentagonal prism. Prisms are a subclass of prismatoids.
An m,n,k-game is an abstract board game in which two players take turns in placing a stone of their color on an m-by-n board, the winner being the player who first gets k stones of their own color in a row, horizontally, vertically, or diagonally. Thus, tic-tac-toe is the 3,3,3-game and free-style gomoku is the 15,15,5-game. An m,n,k-game is also called a k-in-a-row game on an m-by-n board.
Proofs of the mathematical result that the rational number 22/7 is greater than π (pi) date back to antiquity. One of these proofs, more recently developed but requiring only elementary techniques from calculus, has attracted attention in modern mathematics due to its mathematical elegance and its connections to the theory of Diophantine approximations. Stephen Lucas calls this proof "one of the more beautiful results related to approximating π". Julian Havil ends a discussion of continued fraction approximations of π with the result, describing it as "impossible to resist mentioning" in that context.
A hexagonal number is a figurate number. The nth hexagonal number hn is the number of distinct dots in a pattern of dots consisting of the outlines of regular hexagons with sides up to n dots, when the hexagons are overlaid so that they share one vertex.
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.
In mathematics, an alternating sign matrix is a square matrix of 0s, 1s, and −1s such that the sum of each row and column is 1 and the nonzero entries in each row and column alternate in sign. These matrices generalize permutation matrices and arise naturally when using Dodgson condensation to compute a determinant. They are also closely related to the six-vertex model with domain wall boundary conditions from statistical mechanics. They were first defined by William Mills, David Robbins, and Howard Rumsey in the former context.
In spherical geometry, an n-gonalhosohedron is a tessellation of lunes on a spherical surface, such that each lune shares the same two polar opposite vertices.
Graph pebbling is a mathematical game played on a graph with zero or more pebbles on each of its vertices. 'Game play' is composed of a series of pebbling moves. A pebbling move on a graph consists of choosing a vertex with at least two pebbles, removing two pebbles from it, and adding one to an adjacent vertex (the second removed pebble is discarded from play). π(G), the pebbling number of a graph G, is the lowest natural number n that satisfies the following condition:
Given any target or 'root' vertex in the graph and any initial configuration of n pebbles on the graph, it is possible, after a possibly-empty series of pebbling moves, to reach a new configuration in which the designated root vertex has one or more pebbles.
In chemistry the polyhedral skeletal electron pair theory (PSEPT) provides electron counting rules useful for predicting the structures of clusters such as borane and carborane clusters. The electron counting rules were originally formulated by Kenneth Wade, and were further developed by others including Michael Mingos; they are sometimes known as Wade's rules or the Wade–Mingos rules. The rules are based on a molecular orbital treatment of the bonding. These rules have been extended and unified in the form of the Jemmis mno rules.
In mathematics, a Ramanujan prime is a prime number that satisfies a result proven by Srinivasa Ramanujan relating to the prime-counting function.
In graph theory, Vizing's conjecture concerns a relation between the domination number and the cartesian product of graphs. This conjecture was first stated by Vadim G. Vizing (1968), and states that, if γ(G) denotes the minimum number of vertices in a dominating set for the graph G, then
A thrackle is an embedding of a graph in the plane in which each edge is a Jordan arc and every pair of edges meet exactly once. Edges may either meet at a common endpoint, or, if they have no endpoints in common, at a point in their interiors. In the latter case, they must cross at their intersection point: the intersection must be transverse.
Cram is a mathematical game played on a sheet of graph paper. It is the impartial version of Domineering and the only difference in the rules is that players may place their dominoes in either orientation, but it results in a very different game. It has been called by many names, including "plugg" by Geoffrey Mott-Smith, and "dots-and-pairs". Cram was popularized by Martin Gardner in Scientific American.
In the mathematical field of graph theory, the flower snarks form an infinite family of snarks introduced by Rufus Isaacs in 1975.
An integer triangle or integral triangle is a triangle all of whose side lengths are integers. A rational triangle is one whose side lengths are rational numbers; any rational triangle can be rescaled by the lowest common denominator of the sides to obtain a similar integer triangle, so there is a close relationship between integer triangles and rational triangles.
Sumner's conjecture states that every orientation of every -vertex tree is a subgraph of every -vertex tournament. David Sumner, a graph theorist at the University of South Carolina, conjectured in 1971 that tournaments are universal graphs for polytrees. The conjecture was proven for all large by Daniela Kühn, Richard Mycroft, and Deryk Osthus.
In graph drawing, a RAC drawing of a graph is a drawing in which the vertices are represented as points, the edges are represented as straight line segments or polylines, at most two edges cross at any point, and when two edges cross they do so at right angles to each other. In the name of this drawing style, "RAC" stands for "right angle crossing".
In the mathematics of graph drawing, the crossing number inequality or crossing lemma gives a lower bound on the minimum number of edge crossings in a plane drawing of a given graph, as a function of the number of edges and vertices of the graph. It states that, for graphs where the number e of edges is sufficiently larger than the number n of vertices, the crossing number is at least proportional to e3/n2.
{{cite web}}: Missing or empty |url= (help)Bibliography