ANSWERS TO QUESTIONS on HOW TO PLAY SPROUTS handout.

1) Does the game always end?

Sprouts does end. A few observations about the game are helpful. Students should be able to discover that the game can never end with all vertices having degree 3 – the last edge drawn will sprout a new vertex which does not have degree 3. They should also discover that as some vertices get “trapped” topologically while only having degree 2, you can have as many degree 2 vertices at the end as you wish – however, there must be at least 2 vertices of degree 3 for each vertex of degree two at the end. This would result in the following formation, called a “louse” by Conway:

Students should also recognize that a vertex of degree 1 can always have a loop back to itself as another step, and therefore cannot be left at the end of the game.

If we think of each vertex as having 3 places for edges to attach, each turn results in using up two places and adding a new vertex which has one place available. Therefore, each turn result in one less available place for edges overall. Therefore, a game starting with n sprouts must end in at most 3n-1 steps, with at most 4n-1 vertices. One can end with fewer vertices if some vertices get “trapped” as mentioned in the answer to question 1. If each starting vertex first has an edge drawn from itself to itself creating a loop and then an edge connecting the first vertex with the new vertex within the loop, creating a louse, the game ends with only 3n vertices, which is the minimum.

This can be modeled using linear functions and intersections. First of all, we fix the number of vertices we are starting with: let’s say we start with 3 vertices. We can now model a few different quantities with functions:

  • The number of vertices after t turns: v(t) = 3 + t
  • The total possible degree after t turns: dtotal(t) = 3(3 + t) = 9 + 3t
  • The degree used after t turns: dused(t) = 4t (2 edges each taking up two vertices)
  • The degree available after t turns: davail(t) = 9 - 1t (each turn adds 1 vertex or three degrees and uses 4 degrees for the two edges, for a net of the loss of one degree per turn) OR (9 + 3t) – 4t = 9-t (the difference in the last two functions)

To determine when the game ends, we now have a few possibilities:

  • Find when the available degree is 1. This is the intersection of davail(t) = 9 – t with d = 1, which is the lowest possible ending degree. This intersection is when t = 8. Students might correctly think that having a degree of 0 at the end guarantees that there are no more moves, but this is not the first time that there are no more moves; there needs to be available degree of at least 2 in order to draw an edge, one for each end of the edge.
  • Find when the degree used is 1 less than the total degree. This is the intersection of dtotal(t) – 1 = 9 + 3t – 1 with dused(t) = 4t . Again, the 1 is since we cannot take advantage of having only one vertex with available space for a new edge. Students could find where the two functions (without the -1) intersect and know that the game ends in at most 9 turns.

This could be extended by finding similar intersections for 1, 2, 4, 5 vertex starts and find a new table where the independent variable is the number of vertices at the start and the dependent variable is the maximum number of turns in a game. Then we can write a new function that models the maximum number of turns in the game.

Alternately, students can start with n vertices and work with this parameter:

  • The number of vertices after t turns: n + t
  • The total possible degree after t turns: 3(n + t) = 3n + 3t
  • The degree used after t turns: 4t (2 edges each taking up two vertices)
  • The degree available after t turns: 3n - 1t (each turn adds 1 vertex or three degrees and uses 4 degrees for the two edges, for a net of the loss of one degree per turn) OR (3n + 3t) – 4t = 3n - t (the difference in the last two functions)

At this point, we can find the same pairings of intersections to determine an answer. Since we have parameters, students are forced to use algebraic methods to solve rather than graphical methods. Some might be able to extrapolate a general pattern as explained in the first paragraph to determine an answer.

3) Who wins?

To deal with this question completely, students must deal with the issue of graph isomorphism or topological equivalence so that they can discuss which graphs are really the “same.” Two graphs are isomorphic if, loosely, by moving vertices and edges of one graph around, it can be made to look like the second graph without breaking any edges.

Ex 1: These two graphs are isomorphic because the vertex in the middle can be moved to the outside:

Ex 2: These two graphs are isomorphic because we when we move the middle vertex outside, the fourth vertex stays attached to the same two vertex.

Since Sprouts requires that the graphs are planar (edges do not cross) there is also the question of “inside” and “outside” which is not dealt with in graph isomorphism. For example, the following two graphs are isomorphic, but not equivalent with regard to Sprouts since in the second, the black vertices are “outside” and another move can be made.

As students consider which moves they make that are basically equivalent, they should realize that to start a game of Sprouts with any number of vertices, there are basically only two moves: to draw an edge between two vertices or to draw an edge from a vertex to itself. It does not really matter which vertices are used, since it is only the properties of attachment and “inside”/”outside” that are used. They can eventually build up a game tree similar to that given for two-vertex sprouts <link here> although for larger games of Sprouts, this is a very large project. This game tree then can provide data to answer the questions.

a) In the game of two vertex Sprouts, there are essentially 17 different ending games shown in the game tree. (Note that this count can vary depending on what one defines as “different”. I have chosen that “inside”/”outside” choices at the end of the game which do not give different outcomes are essentially the same game.) Of these, 11 are won by the 1st player, so in playing randomly, it might appear that the 1st player has an advantage. Having students test this experimentally is a good introduction to probability and the difference between experimental and theoretical probability. It may also lead them to decide that the choices made about “essentially different” games may not be the most accurate, as they may not reflect the way people think about their choices as they play the game. One could also figure out the theoretical probability by regarding all the vertices as labelled and not dealing with isomorphisms and get a very different probability.

b) Analysis of the game tree for two-vertex Sprouts will show that the 2nd player actually has the winning strategy – that is, that they can make choices that guarantee that they win. One can analyze the game tree by starting from the bottom of the tree and paying attention to who has the choice leading to each result. For example, the first two results in the game tree result in the 1st player winning, so once the first graph in the 4th row is reached, any choice made allows the 1st player to win – even though the 2nd player makes the choice. However, at the next stage up, the series of choices to the right would

result in the 2nd player winning, but the 1st player makes the choice, so they would choose the option to the left, rather than the option to the right, guaranteeing their win. Therefore, from the first graph in the 3rd row, the 1st player has the winning strategy. Working the way up the tree shows that the second player has a winning strategy. If the first player chooses to draw an edge from a vertex to itself in the first move, the 2nd player should choose to connect the vertices of the loop within the loop, since all results from this will result in the 2nd player winning. If the first player chooses to connect the two vertices with an edge in the first move, the 2nd player can then choose the 2nd or third options and from there make choices that will continue to result in his/her win.

These questions can be answered for larger games of Sprouts in the same way, but the data is somewhat unmanageable.

EXTENSIONS:

In Brussel Sprouts, if one starts with n vertices (crosses), the game always ends in 5n – 2 moves, with 6n – 2 vertices. (This is dependent on new vertices being formed by putting a small hash mark across the new edges to form the cross for the vertex.) Therefore, this is a much less interesting game of strategy than Sprouts since one player never has a chance of winning. However, the small change makes the analysis of why the game ends entirely different!

The analysis for why Sprouts ends does not hold here since 2 places for edges are used and added each turn, maintaining the number of available places for vertices. Therefore if we graphed davail(t) it would be a constant function and dtotal(t) and dused(t) would be parallel since the rate of change is the same. Therefore intersections of functions (at least these!) is no longer helpful to solve this problem. The important observation to explain why Brussel Sprouts ends is that when the game ends, each area surrounded by edges contains exactly one arm of a cross. These connected areas surrounded by edges are called faces. To show an example of this, consider the graph below which is the final step in the continuation of the game on the student page. This graph has 11 faces plus the unbounded face which is the rest of the page.

If the face contained two arms of the cross, a new edge could be drawn. Every face must contain at least one arm of a cross since vertices are formed by hash marks, so the last edge which forms the face results in a hash mark being drawn which leaves an arm of a cross in this face.

Then we must use a result of Euler which is from topology. If V is the number of vertices, E the number of edges (here we count as an edge any line between two vertices, so each turn drawn results in two of these new edges) and F the number of faces, including the unbounded ‘outside’ face, then V – E + F = 2 for the ending graph. This ending graph must be connected, which means that we can follow the edges to get from any vertex to any other. If the graph is not connected, we know that we could draw an edge between two different pieces or components of the graph. However, if a graph has k components, V – E + F = k+1. Therefore, at the beginning of the game of n-vertex Brussel Sprouts we have V – E + F = n+1 (n components), but at the end we have V – E + F = 2. The resulting number of faces is the number of open arms of crosses. In the process of the game, there are two possible outcomes from a turn: 1) we connect two components or 2) we draw an edge between two vertices of the same component. Let V’, E’, and F’ count the number of vertices, edges and faces after we take a turn.

  • In the first case, the number of components drops, say from k components to k – 1 component. So if V – E + F = k + 1, then V’ – E’ + F’ = k after the turn. But

V’ = V + 1 and E’ = E + 2, so

k = V’ – E’ + F’ = V + 1 – (E + 2) + F’ = V – E + F’ – 1.

Therefore k + 1 = V – E + F’, so F’ = F.

Note that n-1 of these steps are made to reduce the number of components to 1.

  • In the second case, if V – E + F = k + 1, then V’ – E’ + F’ = k + 1. Since V’ = V + 1 and E’ = E + 2,

k + 1 = V’ – E’ + F’ = V + 1 – (E + 2) + F’ = V – E + F’ – 1.

Since V – E + F’ – 1 = V – E + F, F’ = F + 1.

Suppose there are m such steps. At the start of the game there is one face – the infinite one – so at the end of the game there are m + 1 faces.

The initial available degree is 4n. At the end, we know the available degree is maintained, but is now counting the number of faces, m + 1; therefore 4n = m + 1. Therefore the number of steps is n – 1 + m = n – 1 + 4n – 1 = 5n – 2.

Since the number of vertices we start with entirely determines the number of turns, there is no need to do an analysis of game trees to determine who wins! Using this fact, we know that the first player wins if n is odd since 5n – 2 is then odd and the first player always takes the odd turns. Similarly, the second player wins if n is even. (This allows a simple connection to number theory.)