Transcript Preliminary Presentation

The Game of Nim on Graphs:
NimG
By Gwendolyn Stockman
With: Alan Frieze, and Juan Vera
The Game of Nim
2 players
n piles of disks, with a1,a2, … an amounts
of disks on each pile, respectively
Players take turns decreasing the number
of disks on each pile to any strictly smaller,
non-negative integer
A player loses when there are no disks left
to be removed
Proposed Versions of NimG
 2 players
 1 piece is moved along an undirected graph, and discs
are removed
 If discs on vertices:
 Could move then remove discs
 Could remove discs then move
 If discs on edges:
 Remove discs as you go along an edge
 Players take turns decreasing the number of disks on
each pile to any strictly smaller, non-negative integer.
 How to win:
 If you remove the last disk
 The other player can’t complete their turn
Grundy Numbers
 Used to represent wining and losing
positions
 Given an acyclic diagraph H = (V,E)


( x)  y V : ( x, y)  E x V
 Define:
 Recursively define:
0
x is a sink

G ( x)  

mex( ( x)) otherwise
 A player is in a winning position if at the end
of his/her turn the playing piece is on x V
such that G ( x)  0
Grundy Numbers (cont.)
The Grundy Numbers are calculated in
reverse order, starting from a winning
position
Write a program to calculate the Grundy
Numbers for all possible positions in the
game tree for nimG (which is an acyclic
diagraph)
Previous Work: Nim on Graphs
 Edge version – each edge assigned a nonnegative integer
 Undirected Graphs including:
Bipartite Graphs
Trees
Cycles
 In A Nim game played on Graphs II (Fukuyama)
it was proven that the Grundy Numbers of Nim
on Trees and Nim on Cycles can be found
completely.
My Theorem (Notation)
 (a,b,c):0 means:
a
disks
c
disks
b
disks
v0
v1
v2
 Where is the piece being moved
 Note that my Theorem is for the vertex version
of NimG, with removing disks then moving.
My Theorem
Given non - negative integers a, b, c :
0
1

G (( a, b, c) : 0)  
0
1
0
1

G (( a, b, c) : 1)  
2
0
0
1

G (( a, b, c) : 2)  
0
1
a0
a  0 and b  0
a  b or c  b  1
otherwise
b0
a  0 and c  0 and b  0
a  b or c  b
otherwise
c0
c  0 and b  0
c  b or a  b  1
otherwise
Sketch of Proof
 Note that, by definition:
G ((0, b, c) : 0)  0
G (( a,0, c) : 1)  0
G (( a, b,0) : 2)  0
 For a  0, all possible moves from G (( a,0, c) : 0) result in:
(a ,0, c) : 1
for 0  a  a
and G (( a ,0, c) : 1)  0 so,   ((a,0, c) : 0)  {0,...,0}
thus, G (( a,0, c) : 0)  1.
 Similarly for c  0 , G (( a,0, c) : 2)  1.
 For b  0, all possible moves from G ((0, b,0) : 1) result in:
(0, b ,0) : 0 and (0, b ,0) : 2
for 0  b  b
and both G((0, b ,0) : 0)  0 and G((0, b ,0) : 2)  0 so,
  ((0, b,0) : 1)  {0,...,0} thus, G ((0, b,0) : 1)  1.
Sketch of Proof (cont.)
 If, a  0 and b  0 then 1  G((a,0, c) : 0)    ((a, b, c) : 1)
so, G (( a, b, c) : 1)  1. Note that the same thing
happens for c  0 and b  0.
 If a  0 , b  0, and c  0 then not only is 1   ((a, b, c) : 1)
but, 0  G((a, b ,0) : 2)    ((a, b, c) : 1) b [0, b  1].
So, G(( a, b, c) : 1)  0 and G(( a, b, c) : 1)  1.
 It can be shown that since G (( a, b, c) : 1)  1,
G (( a, b, c) : 0)  1 and G (( a, b, c) : 2)  1 for all nonnegative integers a, b, c.
Sketch of Proof (cont.)
 And, since


  (( a, b, c) : 1)  G (( a, b , c) : 0) b  [0, b  1]


 G (( a, b , c) : 2) b  [0, b  1]
by above, we have 2    (( a, b, c) : 1).
 So, G (( a, b, c) : 1)  2.
 The rest of the theorem is proved by induction.
Next Steps
Prove or Disprove:
Both vertex versions of NimG are special cases
of the edge version, in that they can be
transformed into trees.
Further examine interesting cases with the
bounds on Grundy Numbers
For the remove then move vertex version of
NimG, path of 4 vertices, leads to much higher
Grundy Numbers, than were found for the 3
vertex version.
Questions???