I’ve really been enjoying Zachary Abel’s series of posts on Wythoff’s game [Wythoff’s Game: Red or Blue?; A Golden Observation; The “Fibonacci”est String; Wythoff’s Formula], over on his blog Three-Cornered Things. The Fibonacci numbers show up in the strangest places!
More generally, if you haven’t seen Zachary’s blog before, go check it out. If you enjoy my blog, I think you’ll enjoy his too.
The Math Less Traveled 
(Odd, I can’t seem to leave a comment at Zachary’s blog.)
I’ve seen this game, with one more layer. Paul Zeitz sets this at a pet shop: The two players come in turns to the shop store, and each time have to buy at least one pet. The rules are that they can buy: * As many puppies as they want, or * As many kittens as they want, or * An equal number of puppies and kittens.
We played it a bunch, and only after we’d played it did he show us this graph. I hadn’t noticed that it was queen moves. (Duh.) Fascinating!
Hmm, not sure, maybe your comment is just in moderation?
Anyway, I really like that formulation using puppies and kittens! I’ll have to remember that one. Seems much more accessible than making moves on a chessboard, even though of course they are isomorphic.
One thing I find fascinating is that the presence or absence of “diagonal” plays (i.e. buying equal numbers of puppies and kittens) changes the strategy so drastically. If you are only allowed to buy one type of animal per visit, then it is basically two-pile nim, which is not very difficult to analyze. (Actually, if doing this with a group, this simpler game might make a nice lead-in activity, before introducing diagonal plays?)
But then if you move to three dimensions—e.g. puppies, kittens, and parrots—then even without diagonal moves (i.e. 3-pile nim) the mathematical analysis becomes quite interesting (nimbers, xor, etc.). And I have no idea what it looks like with “diagonal” plays—though I bet someone has thought about it. (There are also several variants to consider—are you allowed to just buy the same number of puppies and parrots, but no kittens? Or do you have to buy the same number of all three types of animal?)
The ‘mad veterinarian’ problem (http://wordplay.blogs.nytimes.com/2011/06/27/numberplay-the-mad-vet/) can be done with more than two types of animals (http://www.bumblebeagle.org/madvet/). Don’t know if it’s mathematically similar or not.
This looks like it’s connected to a problem in the IOI (International Olympiad in Informatics) — I think in 2005. IIRC, you started with a rectangle, and you could cut it either vertically or horizontally at integer sizes, each time keeping the larger piece; the goal was to obtain a unit square (so that your opponent can’t move).
Interesting. I think the twist that makes this one different is “each time keeping the larger piece” — stated in terms of moves on a grid, you are only allowed to move at most half the distance towards one of the axes.
Wow, thanks for the praise! And thank you for noticing the comment bug, Sue; this should be fixed now.
I like the idea of adding “diagonal” moves to higher-dimensional Nim! My gut preference would be to allow subtracting the same amount from any subset of piles, but as Brent said, many variations are possible. This paper briefly discusses a 3D version of Wythoff where 1 or 2 piles may be used at a time, but not all 3. (This is also the only higher-dimensional Wythoff variant I have been able to find.)
Pingback: Visualizing nim-like games | The Math Less Traveled