Simon Rubinstein-Salzedo spoke first. Simon has recently started a a math institute in California's Bay Area with the goal of teaching advanced math concepts to gifted highschool students. In the meantime, he and Urban have worked out some interesting results about a multi-pile Nim variant.
The basic variant of the game starts with a heap of n stones. The first player may take up to n-1 of them. States are described by the pair (pile size, maximum allowed to take), so the initial position is (n, n-1). In future turns, removing k stones from any state (a, b) results in the new position (a - k, 2k). Thus, you can take at most twice as many as were taken last time. (Naturally, you must take at least one stone.)
The analysis of this game employs a new representation of the positive integers that I was completely unfamiliar with: the Zeckendorf representation. Apparently, every positive integer can be uniquely represented as a sum of non-consecutive Fibonacci numbers. For example: 27 = 1 + 5 + 21. Whoa moments:
- Wow, uniquely! Awesome!
- Non-consecutive? Sweet!
- The greedy algorithm works to find the representation. Given n, choose the biggest Fibonacci number below that, include that in the representation, then recurse on the difference. (You can kind of see why the elements must be non-consecutive by induction.
Craig Tennenhouse, my travel buddy, gave the final talk on some variants of Bogus Nim he's created. Poker Nim is a well-understood variant of Nim: you keep a bank of the sticks you've removed and if you have a non-zero amount, you're allowed to add some to one pile on your turn instead of taking any. Unfortunately this doesn't give you any escape from P-positions; your opponent will just snatch up whatever sticks you re-add.
Craig makes two changes to create Non-Loopy Poker Nim:
- First, change this to an impartial game with a shared bank.
- Second, disallow repeated positions to prevent loopiness. (Positions are recorded using multisets, so order doesn't matter.)
If the number of heaps is not fixed, then the game takes on new structure that might best be represented by undirected position graphs. Since loops are not allowed (by tracking the list of moves) this acts like Undirected Vertex Geography, for which winning positions can be easily detected.
Craig came up with another nice game: Rook Nim. This game includes a full n x m checkerboard with a single automatic P-position in one corner and with the rook in the far opposite corner. Here, however, the rook may not move through deleted spaces. This means that not all games will end with the rook moving to (0,0).
Excellent talks! After discussing potential problems to work on, we visited the Board Room and enjoyed the Halifax gaming culture. Today (Wednesday) we worked intensely on the suggested problems: nearly to the point of exhaustion. This was followed up with some more exploring of Halifax and a bunch of rounds of Hanabi.
I've both learned a ton here and will walk away with new results to write up! Only two days in and this has been an amazing conference!