April 06, 2004
pearls before swine 3
Got this link from a coworker.
Play it for a while and you learn to hate Juan. I realized quickly that it's not trivial to find a winning strategy.
I eventually stumbled upon the concept of game states, winning states and losing states. For one row or two rows it's straightforward to prove by induction which states are winning states. For one-row games you should modify the game slightly to make it more interesting: have a row of n stones and allow each player to take for example 1, 2 or 3 stones. What is the winning strategy ? What have all winning positions in common ? (Depends on n).
But even after my coworker gave me a hint saying "binary representation" I couldn't come up with a property that characterizes winning states for games with more than two rows.
Well, after another hint telling me that this game is also known as Nim I found the solution on the web: It falls into the domain of impartial combinatorial games and these two papers give a pretty good description of the theory behind it:
Thomas S. Ferguson: Game Theory
Harold Reiter: Games and Representations
ewd666 part two
This is part two of my weak attempts to solve ewd666 (go here to read part one).
This weekend I tried to attack the problem again and through some dumb luck I think I made some progress.
We left off in part one with the desire to find some property of S that will tell Sam that Paul cannot know the numbers. This time I went to hunt for facts of sums of two integers. The easiest way to hunt is of course with Google. After a few attempts with search terms that didn't yield anything interesting I tried it with "sum prime numbers" since prime numbers always play a big role in number theory problems.
Number one search result for "sum prime numbers" on Google is this page, a pretty interesting read. What caught my eye was Goldbach's Conjecture: every even integer greater than 2 can be written as the sum of two primes.
For our problem this means that S cannot be even. If S were even then Sam couldn't claim that he already knew that Paul cannot know the numbers because S = x + y with x and y prime so Paul could get the numbers from P = x * y.
It's a conjecture but hunting a little further reveals that it has been checked for all integers up to 6 x 10^16 so we're safe with our numbers in the range of [2..99].
This eliminates a lot of cases. I still feel there are way to many cases left so I'm not sure I made progress. It's hard to keep my curiosity in check and not go read the solution. I'm getting weaker, the temptation is great...