Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Grundy | Reply
Nice article! I like these articles containing information related to Div1 1000 problems. (I read it only today)
I have a question on the mapping between Knights and Nim. There is a possibilty -in some cases- to move from a cell with Grundy=1 to a cell with Grundy=2 or Grundy=3. And this does not correspond to Nim. Can you please illustrate this issue?
Re: Grundy (response to post by aminallam) | Reply
The point is that while these moves are possible:
- you don't need them in the winning strategy
- they won't help your opponent in a losing position
so you may just pretend they are not there :)
Re: Grundy (response to post by misof) | Reply
Thank you very much.
Does this mean that we can extend the Nim, so that a player can remove or add any number (other than 0) of coins from one pile, with the condition that the game will converge at last, and we can still apply the xor rule?
Re: Grundy (response to post by aminallam) | Reply
Not really. Without any other restrictions this would lead to a possibly infinite game. At any moment a player may force a "draw" by repeatedly undoing his opponent's moves.

Note that in the horses game you have a measure that causes the game to be finite: the sum of all horses' coordinates decreases. You wouldn't have any such measure in your game. Or, in other words, you need an additional constraint that would guarantee what you called "the condition that the game will converge at last".