Tag Archives: nim

The quarter-circle game

Start at a lattice point inside the quarter-circle x^2 + y^2 < 10^6 in the positive quadrant. You and your opponent take turns: the allowable moves are to go up, right, or both at once (i.e. add (0,1), add (1,0), or add (1,1).) First person to leave the quarter-circle wins. What does it look like if you color a starting point black for “first-player loss” and yellow for “first-player win”? It looks like this:

I like the weird zones of apparent order here. Of course you can do this for any planar domain, any finite set of moves, etc. Are games like this analyzable at all?

I guess you could go a little further and compute the nimber or Grundy value associated to each starting position. You get:

What to make of this?

Here’s some hacky code, it’s simple.

M = 1000
def Crossed(a,b):
    return (a**2 + b**2 >= M*M)

def Mex(L):
    return min([i for i in range(5) if not (i in L)])

L = np.zeros((M+2,M+2))
for a in reversed(range(M+2)):
    for b in reversed(range(M+2)):
        if Crossed(a,b):
            L[a,b] = 0
            L[a,b] = Mex([L[a+1,b],L[a,b+1],L[a+1,b+1]])


One natural question: what proportion of positions inside the quarter-circle are first-player wins? Heuristically: if you imagine the value of positions as Bernoulli variables with parameter p, the value at my current position is 0 if and only if all three of the moves available to me have value 1. So you might expect (1-p) = p^3. This has a root at about 0.68. It does look to me like the proportion of winning positions is converging, but it seems to be converging to something closer to 0.71. Why?

By the way, the game is still interesting (but I’ll bet more directly analyzable) even if the only moves are “go up one” and “go right one”! Here’s the plot of winning and losing values in that case:

Tagged ,

Help me be a great Nim teacher

I’ll be at Marvelous Math Morning at CJ’s school this Saturday, playing Nim with kids ranging from K-5.  One simple goal is to teach them the winning strategy for the version of the game where there’s one pile and each player can draw 1 or 2 chips.  I’ve done that with CJ and he really liked it — and I think the idea of a perfect strategy is one of those truly deep mathematical concepts that even little kids can grasp.

But what else should I do?  What other Nims and Nimlikes should I teach these kids and what lessons should I try to impart thereby?

Update:  First two commenters both mentioned Tic-Tac-Toe.  At what age do kids typically learn how to play Tic-Tac-Toe and at what age have they learned a perfect strategy?  CJ is in kindergarten and has not seen this, or at least he hasn’t seen it from me.  I’ll ask him tonight.

Update:  Nim a success!  I played mostly one-pile, and the kids were definitely able to grasp pretty quickly the idea of winning and losing positions, and the goal of chasing the former and avoiding the latter.  I didn’t encounter anyone who’d played nim before.  I felt some math was transmitted.  Mission accomplished.

Tagged , , ,
%d bloggers like this: