Open Problems and comments about them will go here. We will aim to spend some amount of time on these each class. Post ideas below.
Week 1 - Impartial Game Theory
Erik's Open Problem: Nim for Money:
Suppose we have a new version of the game of Nim (which we will play with coins, instead of nimheaps of stones), where at the end of the game, the winning player will get to take home all the coins they collected from the piles, while the losing player takes nothing. What is the winning strategy for the winner to both win and take the maximum possible number of coins? What is the best strategy for the Nim loser to make the winner take the fewest coins?
Conjecture 1: The winning player always has a strategy that allows him to get at least half of the coins
Counterexample given by Keshav:
Consider the state (3,5,7), where there are heaps of size 3, 5, and 7
coins. As the Nimsum is 1 (111+101+011=001), the state is in N. The only
legal moves are to take 1 coin away from either pile (3+7=4, so 4 must
turn to 4. 3+5=6, so 7 must turn to 6, and 7+5=2, so 3 must turn to 2).
Thus, the P states that (3,5,7) goes to are (2,5,7), (3,4,7) and (3,5,6).
From the first, the losing player can take 7+2=9 coins, so the winning
player gets 1+3+2=6 coins. From the second, the losing player can take
7+3=10 coins, so the winning player gets 1+1+3=5 coins. From the last, the
losing player can take 6+3=9 coins, so the winning player gets 1+2+3=6
coins.
I think that conclusively disproves your conjecture, by counterexample.
Week 3 - Dynamic Programming in Impartial Games
Open Problem: Cram in odd x odd case:
In the even x even board, Cram is 2nd player win, if you take two reflections across the axes. In the even x odd case, it's a 1st player win if the player plays in the middle of the board. What happens in the odd x odd board?
Erik's Conjecture: in any 3 x odd board, besides the 3 x 3 case, moving in the middle as the first move will give the 1st player a win.