A winning move for A is to remove any single line segment. In solving this, we also find that the following graphs are all wins for A (apologies for the ASCII art): o-o-o-o o-o-o-o-o o-o-o-o o-o-o-o-o o-o-o | | | | | | o-o o o-o o o-o O O-O /|\ | | O O O-O O-O \|/ | | O O-O These graphs are all wins for A because A can always remove a path that leaves behind two unconnected line segments, reducing the problem to two identical graphs, which is a forced win for A (because B moves next.) The two graphs on the second row are the only ones you can get if you remove any two line segments from the starting graph. Thus, for A to remove two line segments is suicide. For A to remove one and B to remove one is suicide for B. Thus, when A removes one segment, B must remove two or more line segments. Unfortunately for B, in the cases where it is allowable to remove three or more line segments, the result is a simple path, which is a win for A. The cases where B removes two line segments end up as one of the five graphs on the top row or as a simple path; all wins for A. Thus, A always wins when starting by removing any one line segment. If A removes three or more line segments from the starting graph, the result is either one of the graphs on the first row or a simple path. Thus, A should not remove any more than one segment. -- Ron Parker ------------------------------------------------------------ For a Sympathetic tetrahedrn, the value is 0, as you say, but the options are {*,*3,*4}, the _____ \ / last being \ / with options | | _____ ____ _____ \ \ / \ / \ \ \ , \/ , \ / , \ , , \ | | | | | | | | *3 , 0 , 0 , *2 . 0 , * Richard Guy ------------------------------------------------------------- My name is Richard Hoshino and I am a graduate student at Dalhousie University in Halifax. My thesis will analyze several different "games on graphs", extending previously known results in these games. My final chapter was to be an analysis of an original game I created last month, called PEG (the Path Elimination Game). Alas, as I learned earlier this week, PEG is virtually the same game as Pathos. In this e-mail, I'd briefly like to describe PEG, summarize the results that I've come up with so far, and inquire how this may be extended to examining Pathos. PEG is the same game as Pathos, with one exception. When a player makes a move in PEG by removing the edges from a path, the resulting graph *cannot* have more than one non-trivial component. Thus, while the first five graphs on the www.mathpuzzle.com site (those are the five graphs that have some blue edges) show legal moves in Pathos, only the first three are legal in PEG. My goal is to completely analyze PEG for trees, and so to simplify things, I first considered "rooted path trees", which is a tree formed by taking k paths with a_1, a_2, ..., a_k edges respectively, and attaching all of these paths to a "root" vertex v. We denote such a rooted path tree (r.p.t.) by the k-tuple (a_1, a_2, ..., a_k). For example, the bipartite graph K_{1,6} is the (1,1,1,1,1,1) rooted path tree. And here is an ASCII drawing of a (3,5,4) rooted path tree. . /|\ / | \ / | \ | \ | (note that if k<3, then the rooted path tree is just a simple path, so let us suppose that k >= 3). Since PEG forbids any player from disconnecting the graph into two or more non-trivial components, PEG is equivalent to the following variation of nim: We have k heaps of sizes a_1, a_2, ..., a_k, with k >= 3, and each a_i a positive integer. On any move, you can do one of the following: 1) remove any number of items from one heap 2) completely remove all the items from any two heaps. The last person to play wins. Note: eventually the game is reduced to at most two non-zero heaps, and then the next player to play wins by removing everything (any other move is loony). It is very easy to show that for k=3, the second player wins PEG iff the nim sum of a_1 - 1, a_2 - 1, and a_3 - 1 is equal to 0. In other words, (a,b,c) is a P-position iff the nim sum of a-1, b-1, and c-1 is zero. For k=4, I have come up with several interesting results: Let our r.p.t be (a,b,c,d), with a >= b >= c>= d. If d=1, then (a,b,c,d) is a P-position iff the nim sum of a,b,c is zero. This follows almost immediately from the k=3 case. If c=3 and d=2, then (a,b,c,d) is a P-position iff the nim sum of a-1, b-1, c-1, and d-1 is zero. (In other words, iff the nim sum of a-1, b-1, and 3 is zero). Let's consider c=4 and d=2. Then using Maple, I can verify that (9,5,4,2), (10,7,4,2), (11,8,4,2), and (13,12,4,2) are all P-positions. And after this point, Maple returns the following list of all P-positions with c=4 and d=2: (16,14,4,2), (17,15,4,2), (20,18,4,2), (21,19,4,2), (24,22,4,2), (25,23,4,2), (28,26,4,2), (29,27,4,2), etc. In other words, for a>=b>=14, c=4, and d=2, we have the following result: (a,b,c,d) is a P-position iff the nim sum of a-2, b-2, c-2, and d-2 equals zero. Let's consider c=6 and d=2. Then, (9,8,6,2) is a P-position, and for a>=b>=10, c=6 and d=2, we have the same result as before: (a,b,c,d) is a P-position iff the nim sum of a-2, b-2, c-2, and d-2 equals zero. Finally, let's consider c=4 and d=3. Then (9,6,4,3), (10,5,4,3), (12,11,4,3), and (13,8,4,3) are all P-positions, and for a>=b>=14, c=4 and d=3, we have the same result as before: (a,b,c,d) is a P-position iff the nim sum of a-2, b-2, c-2, and d-2 equals zero. This leads me to ask two questions that I am unable to resolve: 1) I see justify for the cases (c,d) = (4,2), (6,2), (4,3), that after a certain point we have (a,b,c,d) being a P-position iff the nim sum of a-2, b-2, c-2, and d-2 equals zero. But why are there "anomalies" at the beginning? How and why does this happen? Also, what is so special about the ordered pairs (4,2), (6,2), and (4,3)? 2) Using Maple, I have made a list of all P-positions (a,b,c,d) with a<=30, c<=7, and d<=4. From this, I was able to find several beautiful patterns related to the nim sum of the numbers, as described above. However, there is absolutely nothing I see when I make certain lists, e.g. all P-positions with c=5 and d=2. This list is: (12,10,5,2), (13,11,5,2), (17,14,5,2), (18,15,5,2), (19,16,5,2), (21,20,5,2), (25,22,5,2), (26,23,5,2), (27,24,5,2), (29,28,5,2), ... Is there a pattern here? Maybe a better question is, must there be a pattern here? (possibly, there isn't and the other cases were just a coincidence). At this point, I am stuck, and would welcome any ideas. I won't tackle k>=5 until I get a better handle on k=4. Also, I am curious if any of this stuff helps analyze Pathos. ------------------------------------------------------------- Beth Speich Solution For Pathos for K5 2nd player always wins K 5 is a pentagon inscribed inside another pentagon. Label the outer pentagon A and the inner pentagon (i.e. star) B. A move consists of taking edges from A or a combination of edges from A and B (there is an isomorphism of K5 that interchanges A and B). Label the vertices of K5 1-5 clockwise. Thanks to the symmetry of K5, first moves are not sepcific to vertices. If the first player removes any number of edges from A, the second player removes the rest of the edges of A leaving B, a P-position for the second player. So, the only possible moves for the first player involve taking a combination of edges from A and B. The only possible moves that don't form a cycle are 1) AB, 2) ABB, 3) ABA, 4) ABAB, 5) ABAA, 6) ABBA 1) Player 1 removes edges 12 and 25. The second player removes edges 13, 34 and 45, leaving player 1 with a pentagon. P-position for player 2. 2) Player 1 removes edges 12, 25, and 53. Second player removes edge 13, leaving player 1 with bowtie, i.e. 2 triangles. P-position for player 2. 3) Player 1 removes edges 12, 25, 54. Player 2 removes edge 14 leaving player 1 with bowtie. P-position for player 2. 4) Player 1 removes edges 51, 13, 34, and 42. Player 2 removes edges 54, 41, and 12. Player leaves triangle; P-position for player 2. 5) Player 1 removes edges 12, 25, 54, and 43. Player 2 removes edges 14, 42, and 23 leaving Player 1 with triangle; P-position for player 2. 6) Player 1 removes edges 15, 52, 24, and 43. Player 2 removes edges 14, 45 and 53 leaving player 1 with triangle; P-position for player 2. Thus, player 2 wins no matter what. Too bad for player 1. St. Olaf Combinatorics Class Spring '02 under the direction of David "Games Guru" Molnar ------------------------------------------------------------------------ Daniel Hennessy and Mark Thompson also solved K3-3. ------------------------------------------------------------------------ Nathan Stohler demonstrated that A wins on a pentagonal prism, and B wins on the cube, and solved K3,3. I went through all the possible moves for A to show that B always wins the Pathos game on the cube. I started with the one-edge and two-edge moves. We can assume all moves of three or more edges start with 3-4-6, since any two edges will do. I'm sure that some of the moves for A are symmetric (and are repeated below), but I wanted to make sure I covered all possible moves. ---------------------- Chris Lusby Taylor The only winning first move on K3-3 is to erase any one edge. Surprisingly, any legal first move of length n leaves exactly the same graph as any other. ------------------------------------------------------------------------------ Ross Cram 1. Player one (A) removes a diagonal, leaving second player w/ hexagon w/ two diagonals. 2. Player 2 cannot remove any part of the perimeter because then, player one will remove the rest of the perimeter leaving two disjoint line segments. 3.Player 2 cannot remove only 1 diagonal, because then player 1 will take the other diagonal, leaving a polygon(cycle). 4. Player 2 cannot remove a diagonal and part of the perimeter because a. player one can remove the rest of the perimeter and leave player 2 with a polygon. else, b. player one can leave player two with 2 disjoint line segments else, c. player one takes enough of the perimeter to leave player 2 with a tree w/ 3 line segments (a Y shape). 5. Player two cannot remove two diagonals and 1 piece of the perimeter because player one then takes the rest of the perimeter (all that is left) and wins. 6. Player two cannot remove two diagonals and more than 1 piece of the perimeter because player one will be left with a disjoint line segment and a path, so player 1 will take part of the path leaving player 2 with 2 disjoint line segments. 7. Player two cannot remove two diagonals and more than 1 piece of the perimeter because player one will be left with 3 disjoint line segments, player 1 takes one of these leaving player 2 with 2 disjoint line segments. Q.E.D Player 1 wins thanks, St. Olaf College Combinatorics class (10:34am) under the observation of David "Games Guru" Molnar ------------------------------------------------------------------------- Ramprasath Lakshminarasimhan K5 - B wins ___________ Once again label the vertices in any fashion from 1 to 5. Let N be the length of the path played by A in the first move. Note N <= 4 N=4 Without loss of generality (wlg) let the path be 3-5-2-4-1 B then removes 1-3 and gives A, a 5-cycle and wins ! N=3 wlg let the path be 4-1-3-5 B -> 5-2-3-4, giving A, a 4-cycle and wins. N=2 wlg let the path be 4-1-3 B -> 4-2-1-5-3 and again gives a 4 cycle to A ! N=1 wlg let the path be 3-1 B -> 1-4-2-5-3 giving a 5-cycle to A and wins! I think this proves my 1st claim. Here I'll give you the reasoning for my claim namely: B wins on the cube __________________ 6______________7 |\ /| Once again let N denote | \__________/ | the length of the path | |1 2| | moved by A in the first move. | | | | | | | | | | | | | | | | | |4________3| | | / \ | |/____________\| 5 8 (In all the cases below except N=4, B gives A two disconnected copies of the same graph and wins by repeating A's moves from thereon.) N=7 wlg let the path be 1-6-7-2-3-8-5-4 B -> 2-1-4-3 N=6 wlg A -> 6-7-8-5-4-3-2 B -> 5-6-1-2-7 N=5 wlg A -> 1-6-7-8-5-4 B -> 8-3-4-1-2-7 N=4 wlg A -> 1-6-7-8-5 B -> 7-2-1-4-5-6 N=3 wlg A -> 1-6-7-2 B -> 6-5-4-1-2-3-8-7 N=2 wlg A -> 6-7-2 B -> 3-2-1-4-5-8-7 N=1 wlg A -> 6-7 B -> 6-1-4-3-8-7 !! I guess that proves my claim. And lastly, I think A's winning move for K3,3 is removing just one edge. Is it correct ? ------------------------------------------------------- Jim Boyce K5 is a second-player win. It is an example of a large set of second-player wins. If the degree of each vertex is even, then the second play can force a win. The first player makes some move, which will leave two vertices of odd degree. They are, perforce, in the same component. The second player removes some other path that connects those two vertices. This reduces the game to a smaller graph with all vertices of even degree. K3,3 is a first player win. The winning move is to remove one edge. If you remove more, then the second player can remove a path leaving 2 isolated edges. Let's look at the seond player's possible responses. The end points of his path can include 0, 1, or both of the endpoints of you path. That gives us 3 cases to look at: case 0: His path and your path had no endpoints in common. So there are only two vertices of odd degree left. You remove any path that connects them and win (either now, or next turn). case 1: He extended you path to one of your losing first moves. You remove a path leaving two isolated edges and win next turn. case 2: he has extended your edge to a cycle. case 2a: If it is a 6-cycle, then you remove 1 edge and win next turn. case 2b: If it is a 4-cycle, then you remove a path leaving 2 isolated edges and win next turn.