Nim on Graphs by Jonathan D. Clark A dissertation submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama August 4, 2012 Keywords: Nim, Game theory Copyright 2012 by Jonathan D. Clark Approved by Dr. Dean G. Ho man, Professor of Mathematics and Statistics Dr. Pete Johnson, Professor of Mathematics and Statistics Dr. Curt C. Lindner, Distinguished Professor of Mathematics Dr. Chris A. Rodger, Scharnagal Professor of Mathematics Abstract Winning strategies for the Game of Nim on Graphs are discussed. Graphs considered are distinguished from those previously studied in that they may have loops. Winning strategies are found for graphs that have loops and whose links form paths, cycles, trees, or monocyclic graphs. Furthermore, strategies are developed to approach games played on graphs that contain an induced tree with loops. ii Acknowledgments I would like to thank my advisor, Dean Ho man, for his patience and continuous interest in my research. Without the dedication and enthusiasm of the faculty and sta of the Auburn Depart- ment of Mathematics and Statistics, especially those serving on my committee, this work would not be possible. Many thanks also go to my wife, Sarah. Her continual support and encouragement drive me to be a better mathematician and a better human being. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 History of Nim on Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 The Game of Nim on Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Introduction to the Game of Nim . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Paths With Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Cycles with Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4 A Summary of Strategies So Far . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 Trees with Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1 Does Weight Matter? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2 Winning Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3 Extensions to Graphs with Trees as Induced Subgraphs . . . . . . . . . . . . 21 4 Mono-cyclic Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.1 Strategy for Mono-cyclic Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 27 5 Possibilities for Future Research . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 iv List of Figures 2.1 An example of Nim on G played on a multi-graph . . . . . . . . . . . . . . . . . 6 2.2 Games of Nim on G equivalent to traditional nim games . . . . . . . . . . . . . 7 2.3 Gameplay given by an equivalent graph without multiple edges or loops . . . . . 9 2.4 Nim on C4 in which strategy depends on ! . . . . . . . . . . . . . . . . . . . . . 12 2.5 Strategies for games of Nim on paths with loops . . . . . . . . . . . . . . . . . . 16 2.6 Strategies for Games of Nim on cycles with loops . . . . . . . . . . . . . . . . . 17 3.1 Pruning leaves of a tree with loops and associated strategy . . . . . . . . . . . . 22 v Chapter 1 Introduction Before introducing our main topic, the game of Nim on G where G is a multi-graph, we may wish to provide the reader with some basic terminology we will be using to describe the problem and provide some history of the problem in general. 1.1 Background We assume that the reader is familiar with most basic terminology concerning graphs. However, it is worth noting that for a graph, G, we may let context di erentiate between the vertex set and edge set of the graph, writing, for example, v2G should it be clear that v is a vertex. However, in situations for which there may be some ambiguity, we will denote the vertex set as V(G) and edge set as E(G). We denote the degree of a vertex, v, as d(v) and nd reason, on occasion, to distinguish between links of E(G), those edges ending in two distinct vertices, and loops, those incident to a single vertex. Nim is a two player game in which players alternate turns removing objects, often called \stones" from distinct heaps. On a players turn, the player chooses a heap and removes at least one, but as many as all, objects from that heap. Under conventional play, the last player able to remove an object is the winner; that is, a player without the ability to play loses. There are European references to nim from as early as the beginning of the 16th century. It is suspected that the game is much older, but its origins are unknown. The name, nim, and a complete strategy for the game were developed by Charles Bouton in 1901. Nim found a place of particular importance in game theory when Sprague and Grundy independently, in 1935 and 1939, respectively, developed a theory showing the equivalence of an entire class of two player games to nim heaps. Should the sum of games be played 1 in the normal convention, moves and strategy would correspond to a game of nim played on their equivolent heaps. The size of the corresponding heap is called the Grundy number, or nimber, of the game. Games equivolent to heaps are those that are sequential, have 2 players, are impartial games of perfect information, and have no in nite lines of play. A game is impartial if, at a given position, the available moves depend solely on the position and are not determined by the player whose move it is. In such a game, the only di erence between two players is that one player goes rst. We herein denote the rst player P1 and the second player P2. A game is one of perfect information if, at every position of the game, all players know all of the possible moves or combinations of moves that would be known at the end of the game. For example, chess is a game of perfect information; each player knows all combinations of possible moves. Poker is not a game of perfect information. Given a position in a game, options of that position are positions of the game to which the player may move. A game of the type considered by Sprague and Grundy falls into one of two outcome classes. Either it is a won game for the rst player to move under optimal play (called a p-position) or it is a loss for player one regardless of strategy under optimal play (called a 0-position. Here the p- and 0- distinctions are derived from the Grundy number of the game as heaps with a positive or zero size respectfully (the rst being a P1 win by removing all the objects, the second a P1 loss having no options). The key component to strategy in nim is the representation of the size of each heap as a binary number and summing the digits mod2, neglecting to\carry" from one digit to another. This sum of two numbers, x and y, in such a way is called the nim-sum of x and y, and is denoted x y. A game of nim with k nim heaps of sizes n1;n2;:::;nk respectively is a 0-position if n1 n2 ::: nk is 0 and a p-position otherwise. If ni = 0 for every i, n1 n2 ::: nk is 0. If n1 n2 ::: nk is 0 then any option (the reduction of any ni ) will have a 2 positive nim-sum. And if n1 n2 ::: nk is positive then there is an option for which n1 n2 ::: nk is 0. Namely, if the jth digit of n1 n2 ::: nk is the left-most 1, then there is at least one pile whose size, n , has a 1 in the jth digit, and that heap may be reduced to n (n1 n2 ::: nk). For example, consider the game of nim with heaps of size 3, 7, and 6. 3 7 6 is digit addition mod two: 011 111 110 = 010. Each heap has a 1 in the 2nd digit of its binary representation, so reducing 3 to 011 010 = 001 = 1 giving heaps of size 1, 7, and 6 whose nim-sum is 0. Other winning options include reducing the heap of size 7 to 5 or the heap of size 6 to 4. 1.2 History of Nim on Graphs A variation of the game of nim played on a graph, G, was rst introduced by Fukuyama in [3] and extended in [4]. Fukuyama therein determines winning strategies for paths and odd cycles, as well as Grundy numbers for paths, cycles, trees, and certain bipartite graphs. It is important to note that while the Grundy number of a game informs strategy (should the Grundy number of every option of a position be known, perfect play dictates a move to a 0-position), analyzing every option of a position may be overly cumbersome. We are then interested in developing methods by which to recognize whether a position is p- or 0- and to develop an associated strategy that is perhaps less cumbersome. Erickson in 2009 developed a strategy for even cycles, [2]. In the same paper, she is able to develop a winning strategy for games played on the complete graph where all heaps are of size 1. While Fukuyama mentions an equivalence between games on graphs with multiple edges and simple graphs, neither he, nor Erickson, consider strategy or the Grundy number for games played on graphs with loops. Ongoing research seemingly focuses exclusively on simple graphs. We here consider graphs with loops. 3 1.3 Outline In Chapter 2, we will begin with a rigorous de nition of Nim on Graphs, and discuss how the classic game of nim may be thought of as a special case of Nim on Graphs. We will here, imporantly, show that all games on multigraphs are equivalent to games with no multiple edges or multiple loops. Winning strategies for simple cases of Nim on G, paths and cycles, will be given. Since later constructions may depend on strategy or classi cation of these cases, an easy reference gure caps the chapter. In Chapter 3, games of Nim on Trees are discussed. We nd that the structure of trees allows for a recursive reduction of Nim on G to games of Nim on smaller graphs, and we conclude with several theorems extending strategies for nim on trees, allowing for analysis of games played on graphs with induced subgraphs of trees. These latter theorems are put to use with the analysis of games played on mono-cyclic graphs in Chapter 4. Chapter 5 sees a brisk discussion of areas for future research. 4 Chapter 2 The Game of Nim on Graphs 2.1 Introduction to the Game of Nim Here we will de ne the game of nim on a graph, G, simplify the case in general by showing that only a certain class of graph need be considered, and examine winning strategies on paths or cycles with loops in order to get a sense of how loops in particular impact the game. Let G be a multi-graph with loops, edge set E and vertex set V. Positions of the game of Nim on G are ordered pairs, (v;!) with v 2 V, ! : E ! Z+, the set of non-negative integers. The value !(e) is called the weight of e. A position (v0;!0) is an option of (v;!) if there is an e2E incident with both v and v0, !(e) >!0(e) 0, and !0(f) = !(f) for all f2E;f6= e. A player in a position without options is the loser (normal play convention). An example of game played on a multigraph is demonstrated in Figure 2.1. The vertex in each position is denoted using a . In the example, P2 has lost since his nal position has no options; !(e) = 0 for every edge, e, incident with . We classify each position in a game of Nim on G as being either a 0-position or a p-position as follows: A position is a 0-position if it has no options. A position is a p-position if and only if it has at least one option that is a 0-position. A position is a 0-position if all of its options are p-positions. Since from any position, a game must eventually terminate, this does in fact give a classi cation. We note that the traditional game of Nim on k piles, each with pi objects, 1 i k, is equivalent to two di erent formulations of Nim on G: 5 1 2 12 3 1 3 5 2 4 ? 1 2 12 0 1 3 5 2 4 ? 1 2 12 0 1 3 2 2 4 ? 1 2 12 0 1 3 2 2 2 ? 1 2 02 0 1 3 2 2 2 ? 1 1 02 0 1 3 2 2 2 ? 1 0 02 0 1 3 2 2 2 ? 0 0 02 0 1 3 2 2 2 ? P1 P1 P1 P2 P2 P1 P2 Figure 2.1: An example of Nim on G played on a multi-graph 6 p1 p2 pk p1 pk p2 Figure 2.2: Games of Nim on G equivalent to traditional nim games 1. G is the graph with two vertices, one of which is v, and k links, e1;e2;:::;ek. The position is (v;!) where !(ei) = pi, 1 i k 2. G is the graph with a single vertex, v, and k loops, l1;l2;:::;lk. The position is (v;!) where !(li) = pi, 1 i k. The Grundy numbers for such positions are!(l1) !(l2) ::: !(lk) = (or, respectively, the nimsum of the !(ei)), and for each position, there is an option for which !0(l1) !0(l2) ::: !0(lk) = n for each non-negative integer n< . Since we know winning strategies for such positions, and the graphs associated (multiple links and loops) are the basic building blocks of larger graphs, it is natural to attempt to use this relationship to simplify these multiple piles (for us, edges) down to a single pile (edge). Theorem 2.1. Let G be a graph, and (v;!) be a position in a game of Nim on G. G may have multiple loops or multiple links. Then there exists a graph, H, on the vertex set of G in which each vertex is incident with at most one loop, each pair of vertices are incident with at most one shared link, and a position in a game of Nim on H, (v; !), such that a winning strategy in Nim on H corresponds to a winning strategy in Nim on G. Proof. Construct H as follows: if v2V is incident with loops l1;l2;:::;lm in G, then there is a single loop, l, incident with v in H with !(l) = !(l1) !(l2) ::: !(lm). Similarly if links e1;e2;:::;en are each incident with v and v0 in G, then there is a single edge, e, in H incident with v and v0 with !(e) = e1 e2 ::: en. 7 Suppose (v; !) is a p-position in Nim on H with option (v0; !0), a 0-position, and let e be the link incident with both v and v0 in H, corresponding to e1;e2;:::;en in G, where !0(e) < !(e). Then there is an option of (v;!) in Nim on G with !0(e1) !0(e2) ::: !0(en) = !0(e). Similarly, for l, a loop incident with v in H corresponding with the collection of loops incident with v in G, there is an option of (v;!) in Nim on G with !0(l1) !0(l2) ::: !0(lm) = !0(l). Should (v0; !0) be a position with no options, !0(f) = 0 for every edge, f, in H incident with v0 (respectively v should the option reduce the weight of a loop). However, it may be the case that for the corresponding option in Nim on G, (v0;!0), !(fi) > 0 for some i;1 i d(v0). In such a position, suppose (v00;!00) is an option of (v0;!0), and !00(f1) 0 and f is the only edge incident with v0 with non-zero weight. It is clear that in Nim on H removing all of the weight from f is a winning move. A corresponding option exists in Nim on G, and will exist for any future like-options which must be nite since each reduces the nite weight on the edges of G incident with v0. A winning strategy for Nim on H can thusly be translated into a winning strategy for Nim on G, and we may in the future only consider G in which each vertex is incident with at most one loop and each pair of vertices are incident with at most one shared link. Consider the game of Nim on G for the graph, vertex, and weight function as demon- strated in gure 2.1. We may reduce each of the occasions of a multiple edge with a single edge and each occasion of multiple loops with a single loop by adjusting the weight function appropriately. We may discern a strategy for such a position and in doing so appropriate a strategy for our initial game with the small addition of reducing the nim sum of weights back to 0 should P2 play accross such an edge (as they do in our example). The game on a simple graph with at most one loop incident with each vertex and its parallel are demonstrated here in Figure 2.3. 8 1 2 12 3 1 3 5 2 4? 1 2 12 0 1 3 5 2 4? 1 2 12 0 1 3 2 2 4? 1 2 12 0 1 3 2 2 2? 1 2 02 0 1 3 2 2 2 ? 1 1 02 0 1 3 2 2 2 ? 1 0 02 0 1 3 2 2 2 ? 0 0 02 0 1 3 2 2 2 ? 3 12 3 7 6 ? 1?2=3 2?4=6 1?3?5=7?= 3 12 0 7 6 ? 3 02 0 0 0 ? 3 12 0 0 6 ? To reduce7 to 0, we needtochangeeach binarydigit. We candoso by adding7(binary111)toa heap with a 1 inthe4?sdigit.5 (101)hassucha digit. 5?7=2 3 12 0 0 0 ? To reduce6 ? 110to 0,theleftmostdigitsmustbe changed(6?6=0)4 hasa oneintheleftmost digit. 4?6=2 1 02 0 0 0 ? 0 02 0 0 0 ? Wenotethatintheequiv-alent game, P2 haslost,butin theoriginalgame, P2 hasoptions.RecallthatregardlessofP 2 op-tionchosen,thisposition remainsanoptionforP1 0 02 0 0 0 ? Becauseof thefinitenessof the game,therecan onlybefinitelymanysuchoptionsP 2 cantakebeforearrivingata lostposition inbothgames. Figure 2.3: Gameplay given by an equivalent graph without multiple edges or loops 9 2.2 Paths With Loops In order to get an idea of some simple strategies that arise in Nim on Graphs, it is helpful to examine the simple case of a path with loops at some of the vertices. We?ll consider Nim on G, where G is a graph with vertex set fvij1 i ng, and edge set fejj1 j n 1g[flkj1 k ng were ei is incident with vi and vi+1 and li is a loop incident with vi. We can assume that there is a loop at each vertex in the general case since if !(li) = 0, play progresses as if no such loop exists. We will assume, however, that for a starting position, !(ei) > 0 for all i;1 i n 1 Let us rst consider the position (v1;!), and let !(li) > 0 for 1 i m. If P1 chooses option (v1;!0), where !0(l1) = 0, P2 may choose an option (v2;!00). Should !00(e1) > 0, P1 may simply move the position back to v1, reduce the weight on e1 to 0, and P2 has lost. !00(e1) = 0 arrives at a position equivalent to (v2;!jGnv1) in Nim on Gnv1. This position was also an option of (v1;!). If a p-position, P1 can implement the above strategy to reach it. If a 0-position, P1 can choose this option from the starting position, thus (v1;!) is a p-position with strategy determined by the path induced by fvij2 i ng. If !(li) = 0 for 1 i m, all options of (v1;!0) for which !0(e1) > 0 are p-positions (as outlined above) and need not be considered. So we may assume that !0(e1) = 0. The resultant position is a game of Nim on a path. If m = 1, then (v2;!0) is a p-position equivalent to the above case, and (v1;!) is a 0-position. The question of whether (v1;!) is a p-position or a 0-position resides entirely on the parity of m. Since perfect play removes all weight with each option taken, (v1;!) is a p-position for even m and a 0-position for odd m. But what of strategies for games of Nim on G where G is a path with loops but the starting position is not (v1;!), but rather (vi;!) for some i, 1 0 (similarly for !0(ei 1) > 0), since P2 would then have the option of reducing the weight on ei to zero, moving the position back to vi, a position, which as previously analyzed, would be a 0-position. If !(li) > 0, then (vi;!) is a p-position. As before, if either of (vi 1;!i 1) or (vi+1;!i+1) are 0-positions it is clear. If both are p-positions, (vi;!0) where !0(li) = 0 is an option of (vi;!) and a 0-position by the above argument. The important points that we might draw from this case are: 1. (v1;!) is a p-position in Nim on G if !(l1) > 0. The existence of weight on a loop at the starting position gives P1 a great deal of power. P1 may stall by reducing the weight on l1 to 0 and force P2 to move to v2 or may reduce the weight on e1 to 0 placing P2 on v2 depending on whether v2;!jGnfv1g in Nim on Gnfv1gis a p-position or a 0-position respectively. 2. The winning strategy for a game of Nim on G, where G is a path with loops, depends only on the existence of weight on an edge, not on the amount of weight on an edge. If !(e) = 1 for every e2G, p-positions and 0-positions are preserved for initial positions based on their vertex. 3. Our most natural approach is to analyze each of the options of (v;!). However, this can be cumbersome. There may be a great many options, but we might pay particular attention to those that reduce the weight of an edge to 0. These correspond to nim on the subgraphs of G missing an edge incident with v. 2.3 Cycles with Loops Since we now have an easy way to categorize games of nim on paths with loops as p-positions or 0-positions and developed strategy for these cases, it is natural to look at the case of cycles with loops since options for these games will include options equivalent to 11 2 11 1 ? 0 11 1 ? 1 11 1 ? 2 10 1? 0-positionp-position Figure 2.4: Nim on C4 in which strategy depends on ! games on paths with loops. We?ll here consider G to be a cycle on n vertices with vertex set fv0;v1;v2;:::;vn 1gand edge setfe0;e1;e2;:::;en 1g[fl0;l1;l2;:::;ln 1gwhere ei is a link incident with vi and vi+1 mod n, and lj is a loop incident with vj. Without loss of generality, we will assume the starting position is (v0;!). It is instructive here to note that while the amount of weight on the edges of a graph had no import on strategy in the case of paths with loops, the weight may well be important to the classi cation of positions of Nim on G if G is a cycle. Consider the case when n = 4, !(e0) = 2, !(ei) = 1 for i6= 0, and !(lj) = 0 for all j. (v1;!0) where !0(e0) = 0 is an option of (v0;!), but is a p-position as it is equivalent to a loopless path of length three with a position at a terminal vertex. However, should !0(e0) = 1, P2?s only options will be such 0-position paths. Thus (v0;!) is a p-position, but P1?s winning strategy involves reducing the weight of an edge to a non-zero value. 12 Strategy for cases for which !(li) = 0 for all i are discussed in detail in [3] (odd cycles) and [2] (even cycles). These cases are here considered as special cases of cycles with loops, and we have arrived at the associated strategies independently. We rst consider cycles for which !(l0) = 0 but !(li) > 0 for some i6= 0. If we can easily classify these positions, we can use those that are 0-positions to help classify positions for which !(l0) > 0 with these 0-positions are options. For the sake of simplicity "vertices counter-clockwise (CCW) of v0" will refer to the vertices vn 1;vn 2;:::;v1;v0, in that order, while the "vertices clockwise (CW) of v0 will refer to v1;v2;:::;vn 1;v0, in that order. Let !(lk+1) > 0 and !(li) = 0 for 0 i 0 and !(lj) = 0 for j( modn) n m. If either of k or m are odd then (v1;!0cw) (or respectively (vn 1;!0ccw)) where !0cw(e0) = 0 (resp. !0ccw(en 1) = 0) is an option of (v0;!) and is a 0-position, being equivalent to a path with loops that is a 0-position. If both k and m are even, the same options are p-positions. However, options in which !0cw(e0) > 0 or !0ccw(en 1) > 0 are also p-positions since (v0;!00) where !00(e0) = 0 or !00(en 1) = 0 would be 0-position options. Even k and m must then imply a 0-position. If !(l0) > 0, even k and m would imply a p-position with option (v0;!0) where !0(l0) = 0, a 0-position. If either of k or m are odd and !(l0) > 0 and !(li) > 0 for some i, 1 i n 1, then, as before, (v1;!0cw) (respectively (vn 1;!0ccw)) where !0cw(e0) = 0 (resp. !0ccw(en 1) = 0) is an option of (v0;!) and is a 0-position, being equivalent to a path with loops that is a 0-position. The loop at v0 does not change the parity of the number of loops for which !(li) = 0 preceding a loop with positive weight on the path that is an option of the initial position. We are left then with cases for which !(li) = 0 for all i> 0. If n is odd and !(l0) = 0 options for which !(e0) or !(en 1) are zero are 0-positions since they are equivalent to paths for which the initial position is on a terminal vertex and the path begins with an odd number of loops for which the weight is zero. Nim on Odd Cycles for which !(li) = 0 and !(ei) > 0 13 for all i are P1 wins. Likewise if n is even and !(l0) > 0, options for which !(e0) or !(en 1) are 0-positions and (v0;!) is a p-position. For odd n, if !(l0) > 0, similar options (where one of !0(e0) or !0(en 1) are 0) are p-positions equivalent to paths. Options for which !0(e0) > 0 or !0(en 1) > 0 are p-positions for cycles as outlined above. Reducing the weight on l0 to zero is also an option, but a p-position. Thus, if !(l0) = 1, the only options of (v0;!) are p-positions, and (v0;!) is a 0-position. Should !(l0) > 1, reducing the weight on l0 to one is a 0-position option available to P1. In this case, the weight on the loop, l0 is of consequence, but only in so much that it is either one or greater than one. We now consider the case for which n is even and !(li) = 0 for all i. For any position, (v;!) in which !(ei) > 0 for all i, all options for which !0(ei) = 0 for some i are equivalent to a game of nim on a path with loops with initial position at a terminal vertex and with an odd number of vertices sequential from the initial position without loops and are thus p-positions. For P1, any hope of nding a 0-position option resides in reducing the weight of an edge incident with v0. Since edges for which !(ei) = 1 may only be reduced to a weight of zero, e ectively "breaking" the cycle and placing the subsequent player in a p-position, we may be particularly interested in positions at vertices incident with edges with weight one, and those positions with options that include such vertices. We may then classify any positions, (v0;!), for which !(e0) > 1 and !(en 1) > 1 and for which !(e1) or !(en 2) is one, as p-positions, since, (v1;!0), where !0(e0) = 1), or respectively vn 1;!0) where !0(en 1) = 1, are options and 0-positions. Suppose !(ei) = 1 for some i, 0 i n 1. Let m be the smallest value of i for which !(ei) = 1 and M be the largest. Assuming optimal play, we know that any position, (vi;!), where i = m 1 or i = M + 2 are p-positions. We need not consider positions or options (vi;!) for which m 1 i M + 2 since we are assuming best play. We may then disregard weight on any of the edges in feijm+ 1 i M 1g. The game is then reduced to play on a path, but one in which, under optimal play, weight is not reduced to zero, edges 14 for which !(e) = 1 will not be crossed should another option be available. If either of m or n M are odd, P1 has a winning strategy by chosing option (v1;!0) where !0(e0) = 1 or respectively (vn 1;!0) where !0(en 1) = 1. P2 is then forced to break the cylce, a p-position for P1, or to reduce the weight on e1 (respectively en 2). If !00(e1) > 1 then (v1;!000) where !000(e1) = 1 is an option and a 0-position. If !000(e1) = 1, P1 may reduce the weight on e2 to one, and play will continue in a like manner until P2 is in the 0-position, (vm; !), where !(em 1) = !(em) = 1. 2.4 A Summary of Strategies So Far We nd that it may be helpful to have a visual reference for winning positions and strategies for the games so far discussed. Many are easily analyzed at rst glance, and thus, a diagram representing p-positions and their related 0-options, here discussed, may be of use. In the associated diagrams, the deletion of an edge in a move is associated with the removal of all weight on that edge. In the case of cycles, we restrict ourselves to de ned option of changing the weight of an edge to zero. As before, the vertex of the initial position is denoted with a . 15 v1 v2k ? v1 v2k?1 ? v1 v2k?1 ? 0-position ? ? ? ? ? evennumber of looplessvertices oddnumber of looplessvertices ? path terminates or reachesloopedvertex path terminates or reachesloopedvertex path terminates or reachesloopedvertex path terminates or reachesloopedvertex InitialPosition dashedloopsmay have positive orzeroweight Strategy Figure 2.5: Strategies for games of Nim on paths with loops 16 ? odd ? 0 ? eveneven ? 0 ? eveneven 0-position ? noloops.?evennumberofvertices Winningstrategyandclassificationdepend ontheweightassignedtotheedges ? loopat?only. ?oddnumberofvertices Winningstrategyandclassificationdepend ontheweightassignedtotheloop Figure 2.6: Strategies for Games of Nim on cycles with loops 17 Chapter 3 Trees with Loops 3.1 Does Weight Matter? As we saw in Chapter 2, the existence of a cycle in a graph has the potential to complicate the Game of Nim played on that graph, introducing situations in which the weight assigned to an edge alters whether a position is a p-position or 0-position. Since trees have no cycles, we may suspect that their structure might make for a simpler analysis. Fukuyama addresses Nim on Trees in [4] and nds the Grundy numbers completely for such games. We?ll here consider trees that have loops at some vertices. The case for which the weight on these loops is 0, that is the case for which Fukuyama previously found winning strategies, is of course included as a speci c instance of Nim on such graphs. Theorem 3.1. For games of Nim on G with initial position ( ;!) in which G is a tree with loops, the classi cation of ( ;!) as a p-position or 0-position, is independent of whether !(e) = 1 or !(e) > 0 for any e2G. Proof. Without loss of generality, we assume that !(e) 1 for any e2G. Consider the components of Gnf g, fTij1 i ng, and the vertices adjacent to , fvij1 i ng, where vi 2Ti and and vi are adjacent by edge ei. In Nim on Ti, each of (vi;!jTi) are p-positions or 0-positions. If any such games are 0-positions, say (vk;!jTk), then (vk;!0) where !0(ek) = 0 is a 0-position and option of ( ;!). ( ;!) is then a p-position. If there is no loop incident with and each of (vi;!jTi) are p-positions, any option, (vi;!0), of ( ;!) for which !0(ei) = 0 is a p-position and is not a perfect play option for P1. If P1 choses an option, (vk;!0) where !0(ek) > 0, P2 has the option ( ;!00) where !00(ek) = 0. If P1 continues to avoid options that reduce the weight on an edge incident with to zero, 18 this strategy may be repeated until P1 is in the position ( ; !) where !(ei) = 0 for all i which is a 0-position as it has no options. Thus, if there is not a loop incident with , ( ;!) is a 0-position. If there is a loop incident with , then reducing the weight on the loop to zero places P2 in a 0-position and ( ;!) is a p-position. The strategy for the initial move in Nim on a Tree does not depend on the weight of the edges, only the existence of weight. The same argument holds for any future positions in the game, and thus winning strategy and the classi cation as a p- or 0-position is independent of whether !(e) = 1 or !(e) > 0 for any e2G. 3.2 Winning Strategies So, we know that additional weight on any edge with positive weight will not change whether a position is won or lost, and we know that any position, ( ;!) for which there is a loop at , is a p-position. We are not, however, directed to a winning strategy by this information since analysis of the games played on each of the Ti isn?t provided beyond a recursion of the above argument which seems prohibitively time consuming. We have noted that if P2 is in a 0-position and removes weight from an edge without removing all of the weight, the P1 may remove the remaining weight from the edge and place P2 back into a 0-position. By assuming such a strategy, if ( ;!) is the initial position, for any P1 position, (vk; !), we may assume that !(ei) = 0 for every ei, 1 i k, in the path e1v1e2:::vk 1ekvk. If !(ek) > 0, then the previous strategy o ers the 0-position (vk 1; !0) where !0(ek 1) = 0. This fact allows us to develop a recursive algorithm by which we may reduce the game of Nim on G where G is a tree with loops to that of a game of Nim on a star. Such an algorithm is advantageous since the classi cation of a game played on a star where the initial vertex is the center is easily deduced: If there is a loop incident with , ( ;!) is a p-position. 19 If there is a leaf that is not incident with a loop (or for which the weight of the loop is 0), ( ;!) is a p-position. If there is no loop incident with , and each leaf is incident with a loop with positive weight, ( ;!) is a 0-position. The winning strategy for p-positions in such games is also easily identi ed. If there is no loop with positive weight incident with some vi, remove the weight on that edge; if there is a loop with positive weight on every vertex of G, remove the weight on the loop incident with ). Theorem 3.2. Let G be a tree with loops, where G is not a star, and let the initial position of a game of Nim on G be at 2V(G). Then there is a graph, G , where: 1) V(G ) V(G) 2) V(G)nV(G ) is comprised of leaves of G 3) E(G )nflij1 i ng E(G) where flij1 i ng is a (potentially empty) set of loops incident with a subset of leaves in G 4) If ( ;! ) is a p-position in Nim on G , then ( ;!) is a p-position in Nim on G where ! (e) = !(e) for every e2E(G )TE(G) and ! (li) > 0 for all i, 1 i n. Proof. Since G is a tree, and G is not a star, there exists at least one vertex v2G, v6= , such that the neighbor set of v, fvij1 i kg, consists of at least k 1 leaves. That is, at most one of the k neighbors of v is incident with more than one link. If play were to progress with perfect play following the earlier outlined strategy countering options for which a player does not remove all weight from an edge, we may assume that shoud a position (v; !) be reached, !(ei) = 0 for every edge, ei, in the path from to v. Any position in Nim on G at v will be equivalent to a game of Nim on a star with center v and leaves, the leaves of v in G. Thus, the position may be labeled p- or 0- according to the clear strategy outlined above. Should (v; !) be a p-position, we can delete the leaves of G and assign a loop at v with positive weight without changing the classi cation of ( ;!) as a p-position or 0-position. Likewise, if (v; !) is a 0-position, the leaves may be deleted 20 and for any loop, l, incident with v, ! may be rede ned so that !(l) = 0, ensuring that the one possible option at v under the employed strategy is a 0-position. By replacing the star graph with a graph that is also a p-position (respectively 0-position) we do not change the classi cation of the initial position as the classi cation of any options at subsequent vertices have not changed. The algorithm outlined here may be used recursively to reduce a game of Nim on a Tree to the game of Nim on a Star centered at at which point ( ;!) may be easily classi ed as a p-position or a 0-position as outlined above in the strategy on stars. Since every option of a game of nim on a tree with loops is also played on a tree with loops, we can use the property that positions at a vertex for which a loop is incident are p-positions together with the inconsequence of weight to better the algorithm by which G is truncated. If v 6= is a vertex incident with a loop for which the weight is positive, every vertex u for which v is in the path from to u may be deleted without changing the classi cation of ( ;!). However, the advantage of the previous algorithm is that each step of the recursion also outlines optimal strategy for P1 at each step, provided that ( ;!) is a p-position or for P2 should it be a 0-position. Strategy is easily determined by considering the star pruned at each iteration. An example of the pruning algorithm as well as the associated strategy for P1 is demonstrated in Figure 3.1. 3.3 Extensions to Graphs with Trees as Induced Subgraphs A similar argument may be made for games of nim on graphs with a "tree-like" structure. Given that a graph, G satis es certain properties that allow us to incorporate such an argument, and knowing strategies for games of Nim played on speci c subgraphs of G, we would be able to either classify positions in Nim on G as p- or 0-, or alternatively, we would be able to consider a game of nim played on a graph similar to G but with fewer edges. 21 ? ? ? ? P1 ? ? P2 ?= ?= ?= ?= ? P1 ? Figure 3.1: Pruning leaves of a tree with loops and associated strategy 22 Theorem 3.3. Consider a game of nim on a graph, G, with position ( ;!), for which the vertices of a graph, G, may be organized into sets, the induced graphs of which are labeled Gi, 1 i n, and T where: 1) T is a tree with loops 2) V(Gi)TV(T) =fvig, for every i, where vi is a leaf in T 3) If a link of G is incident with vertices u and v, u2Gi, and v2Gj, then i6= j Then ( ;!G), a position in a game of Nim on G with 2T, is a p-position (respectfully 0-postion) if ( ;!T+) is a p-position (respectfully 0-position) in a game of Nim on T+ for a graph T+ where: E(T) E(T+) E(T+)nE(T) =flig , a set of loops incident with the vertices, vi !G(e) = !T+(e) for every e2T, and !T+(li)2f0;1g for every i Proof. Since Gnf g is a graph of components equal to the number of links in G incident with , each component represents an option of ( ;!G) at a neighbor of v, each is a p- position or a 0-position, and the argument presented in Theorem 3.1 applies to the position in a similary way: if ( ;!G) is a p-position, P1 has a wining strategy that does not depend on the weight of the edges incident with , and likewise for P2 if ( ;!G) is a 0-position. The argument applies for all positions on vertices in Tnfvig, and so as gameplay progresses, we may assume that for a future position, (v; !), !(e) = 0 for all links,e, in the path from to v, where v2T. A position (vi; !) would then only have options on a game equivalent to Nim on Gi. Just as in Theorem 3.2 we can trade such star subgraphs for positions sharing a p- or 0- classi cation, we here construct T+ by deleting the vertices of Gi, for each i. If there is no loop incident with vi and (vi;!jGi) is a p-position in Nim on Gi, then add a loop, li incident with vi, to Gi. De ne !T+ such that !T+(li) = 1 for every i and !T+(e) = !(e) for every e2TTT+. 23 We note the amount of weight placed on li is inconsequential since the underlying graph is a tree with loops and that the addition of the loop can not a ect play for positions at vertices elsewhere in T+ since we implement an optimal strategy as outlined above which prevents play from returning to a vertex of T, a tree, and since the vertex sets of the various Gi are mutually exclusive. We can see then that if a graph G has a tree with loops as an induced subgraph, nice properties that were of aid in our analysis of trees with loops can be extended to Nim on G. It is worth noting, however, that in order to determine the strategy for play from initial position ( ;!), strategy on the subgraphs, Gi, must be known, and that while there may be tree structures which allow us to categorize ( ;!) as p- or 0- , in general a classi cation of (vi;!jGi) as p- or 0- in Nim on Gi may need to be known in order to arrive at such a classi cation of ( ;!). However, provided that such strategies are known, the recursive algorithm outlined in Theorem 3.2 may be utilized to provide strategy for P1 at each step in order to win the game provided ( ;!) is a p-position (or P2 should it be a 0-position). The game of Nim on G in such a case would not be solved completely since Theorem 3.3 requires that be a vertex in T, the tree portion of G. We might suspect that the induced tree with loops would still be a helpful structure. Indeed, we can "prune" edges from T as in Theorem 3.2, but knowing strategies for the induced subgraph inluding in such a case would not necessarily be helpful as we will see. Theorem 3.4. Let be a graph with vertices and v, (v may equal ), for which the vertices of may be organized into two sets with induced subgraphs T and G with: 1) T a tree with loops 2) V(T)TV(G) =fvg 3) v is a leaf in T Then there is a graph, G+, G G+, for which a game of Nim on with initial position, ( ;!), 2G, is equivalent to a game Nim on G+ with position ( ;!G+) where: 24 G+ is G with the addition of dT(v) pendant edges incident with v which may have loops incident with the neighbors of v. These loops are not necessarily elements of E( ). !(e) = !G+(e) for every e2E(G), and !G+(l) = 1 for every loop, l2E(G+)nE(G) Proof. We construct G+ be pruning the leaves of T according to the algorithm outlined in Theorem 3.2 treating v as the vertex for the inital position in a game of Nim on T. We must then show that if ( ;!) is a p-position (respectively 0-position) in Nim on then ( ;!G+) shares the classi cation in Nim on G+, when G+ is so de ned. If vt2T, all trails from to vt include v, thus, a position (vt;! ) can only be reached after a position at v. We will rst then examine positions at v, since if the classi cation of such positions are retained then so is the classi cation of ( ;!). Let ftij1 i dT(v)g denote the vertices incident with the pendant edges in G+ adjacent to v and suppose that (v;!v) is a p-position in Nim on . If there is a ti which is not incident with a loop in G+, then (ti;!0v) where !0v(vti) = 0 is clearly a 0-position option in Nim on G+, but is also a 0-option in Nim on as de ned in the algorithm from 3.2. If there is a loop at each ti in G+ then no option for which !0v(vti) = 0 is a 0-position in Nim on G+ or in the corresponding Nim on . The winning option in Nim on at v can be mirrored in Nimo n G+ and the must be a winning option that is not at some ti since P2 could move back to v, and since it was obstensibly from a 0-position P1 would again be at a p-position at v. This argument hold for any future positions at v and thus (v;!v) must also be a p-position in Nim on G+. If (v;!v) is a 0-position in Nim on then each of the ti will be incident with a loop. All gameplay in Nim on mirrored in Nim on G+ that progress on the vertices of G will not change the classi cation. Options for which !0v(vti) = 0 are clearly p-positions, and if !0v(vti) > 0, P2 can reduce the weight of the edge vti to zero for each i and the strategy on the vertices of G may be followed. 25 As we see in the next chapter, these generalizations of the strategy for trees allow us to approach nim on graphs which are composed of subgraphs with which we have experience - namely, trees and cycles. 26 Chapter 4 Mono-cyclic Graphs While Theorems 3.3 and 3.4 allow us to reduce the classi cation of a position in Nim on G to classifying games on relatively simpli ed graphs, in both cases, we are limited in that we must know strategies or outcomes for either certain induced subgraphs of G, or strategies for induced subgraphs plus a collection of pendant edges. We would like to apply these theorems to classes of graph for which such strategies are known or can be deduced, which leads us to consider mono-cyclic graphs. For our purposes, it is helpful to picture such graphs as cycles with trees extending from some selection of vertices on the cycle. As before, loops are allowed in the edge set. 4.1 Strategy for Mono-cyclic Graphs It is su cient to consider positions, ( ;!), for which is on the cycle in G. If such positions may be classi ed as p-positions or 0-positions and a strategy for such games is known, then we may apply Theorem 3.3 in order to classify and determine strategy for positions in which is not on the cycle. Let G be a mono-cyclic graph, and consider position ( ;!) in a game of Nim on G, where is on the cycle in G. We may apply Theorem 3.4 to equate G to a graph in which the trees extending from the vertices in the cycle of G are limited to pendant edges that may have loops. Thus we assume that G is a cycle with a collection of pendant edges and loops. We will letfvij1 i n 1gdenote the non- vertices of the cycle in G, labeled in order from . Furthermore, we will often herein use the convention of referring to the edge incident with the vertices u and v as simply, uv. 27 Case 1 : is adjacent to a pendant vertex, u, which itself is not incident with a loop. (u;!0) where !0( u) = 0 is a 0-position and an option of ( ;!). Thus ( ;!) is a p-position with winning strategy reducing the weignt on edge u to zero and, if necessary, letting play progress on the tree associated with the pendant edge. Case 2 : There exist at least two vertices in fvij1 i n 1g adjacent to pendant vertices without loops. Let v and v , < , be the vertices adjacent to loopless pendant vertices, u and u respectively, for which no vi is adjacent to a loopless pendant vertex when i < or i > . Positions (v ;! ) and (v ;! ) are p-positions since each has a zero option, reducing the weight of the edge v u (respectively v u ) to 0. Positions (vi;!i) where 0, the resulting position has a path Tk, similarly de ned as above, which is a p-position. Speci cally, the path will consist of an odd number of loopless vertices starting at v1 before the path terminates or a looped vertex is reached. However, if !0( v1) = 0, the verticesfvkj + 1 k n 1gmay be deleted as argued above and the path with loops on which play would progress would be a p-position. All options of ( ;!) are thus p-positions, and ( ;!) must be a 0-position. Strategy for P2 in such a game, assuming again P1 chooses an option at v1, is to choose an option at v2 removing all weight from edge v1v2. Case 4 : There are no vertices in the cyclic subgraph of G adjacent with a pendant verex with a loop. As discussed in Case 3, no winning strategy will necessitate play that reduces the weight of a pendant edge whose pendant vertex is incident with a loop. Play in this case, therefore, may be thought of as entirely restricted to the subgraph induced byf gSfvij1 i n 1g. The position is p- or 0- according to the classi cation outlined in Chapter 2?s discussion of 29 nim on cycles with loops. Strategy is likewise de ned. When this strategy culminates, there may be options on a pendant edge with a loop. However, such a position is a 0-position and strategy mirrors play for other pendant edges considered in this case. 30 Chapter 5 Possibilities for Future Research Perhaps the most glaring open question left at the conclusion of this work is, "For games of Nim on G where G is a graph discussed herein, determine the Grundy number for an initial position, ( ;!)?" One may recall that Grundy numbers for paths and cycles without loops are found completely in [4]. The use of these Grundy numbers is interesting in a couple of di erent ways. In terms of strategy, if the Grundy numbers for all of the options of ( ;!) could be found, P1 would know that any option for which the Grundy number was zero would be perfect play. Induced subgraphs of trees are themselves trees, so a nding Grundy numbers for games on trees with loops would allow for such an analysis at any position in the game. More broadly, the ability to nd the Grundy number for a position and its options would provide a strategy for the sum of these games. If all games considered were Nim on Graphs, we could imagine a graph with k components, each component with a game piece placed at a vertex. On a players turn (s)he would choose a component and make a play with the corresponding game piece in a game of nim on that component. This game would be equivalent to a game of nim with k heaps, with each heap corresponding to a component, the Grundy number for which would give the number of objects in the heap. The introduction of other game pieces in Nim on G may lead us to consider games on a connected graph, G in which each player is given a distinct game piece, or in which a player were allowed to choose from a selection of game pieces and then make a move on his/her turn. One easily sees that such a variation of Nim on G complicates analysis of the game greatly. 31 As for other graphs to consider for analysis, I have begun consideration of games played on a theta graph with loops. The theta graph seems a natural problem to approach since its induced subgraphs are trees or mono-cyclic graphs. Since strategies for games played on these graphs are known, Theorems 3.3 and 3.4 are of some use. However, the ability for gamplay to proceed onto cyclic subgraphs at multiple vertices, as well as the fact that such graphs have three induced cycles (on which weight assigned by ! may a ect strategy and classi cation), necessitate a more careful analysis. It would be interesting to nd criteria for G that would indicate whether the amount of positive weight on an edge would be signi cant. Erickson has approached the complete graph, developed a winning strategy in general when !(e) = 1 for every e2Kn, and for small values of n shown that the amount of positive weight placed on any edge does not change the classi cation of ( ;!) as a p-position. Her proposed strategy for the "!(e) = 1 8e 2 Kn" case is easily extended to a case where loops are added at every vertex. To my knowledge, however, no work has yet been done on the complete graph where every vertex is also incident with a loop for n 4 and ! is unrestricted. 32 Bibliography [1] Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. "Winning ways for your mathematical plays. Vol. 1." A K Peters Ltd., Natick, MA, second edition, 2001. [2] Lindsay Erickson, "Nim on the Complete Graph." accepted for publication, Ars Com- binatoria, 2009. [3] Masahiko Fukuyama. "A Nim game played on graphs." Theoret. Comput. Sci., 304(1- 3):387399, 2003. [4] Masahiko Fukuyama. "A Nim game played on graphs. II." Theoret. Comput. Sci., 304(1- 3):401419, 2003. 33