#!/usr/bin/python
# Today at the IBL workshop we did a fantastic bit of playful mathematics. Gulden Karokok introduced us to a mathematical game and encouraged us to play it together. As soon as we had played a couple matches, everyone started to conjecture about winning strategies. The questions emerged naturally from the play and the whole room erupted in discussion. It was a perfect example of the mathematics generating the inquiry
# The game is quite simple: Two players have some number $latex N$. They have the following moves: they can subtract one or they can "half it". If $latex N$ is even, you half it by dividing by two. If $latex N$ is odd, you half it by subtracting one and dividing by two. A player loses if the number is zero. Players alternate turns until they reach zero.
# The game is a nice little exercise in division. It could be good exercise for people learning arithmetic. However, it gets boring quickly. The natural questions are much more interesting: How wins? What's the optimal strategy? These questions raise all sorts of fascinating problems both notational and mathematical. Lots of discussion groups puzzled over the question "What is a winning number? Should it be when the current player can force a win or when the next player can force a win?"
# After chasing around examples $latex N < 7$ on a page, I decided to take an algorithmic approach. Once I convinced myself that I could write up and algorithm for the problem, I tuned out of the workshop and wrote some code to generate all winning.
# I wanted to write some code which would figure
The following python code uses a brute-force approach to computing winning states.
def wins(k):
"determine whether a player can force a win [1] or loses [0] from state k"
if (k==0):
return 0;
if (k%2==0 and k>0):
# we can divide by two
# we can subtract one
if (wins(k/2)==1 and wins(k-1)==1):
return 0;
if (wins(k/2)==0 or wins(k-1)==0):
return 1;
if k%2==1:
# we can subtract one
# we can (x-1)/2
if (wins((k-1)/2)==1 and wins(k-1)==1):
return 0;
if (wins((k-1)/2)==0 or wins(k-1)==0):
return 1;
for x in range(0,100):
print x , "-->" , wins(x);