JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Div2-500 proof | Reply
The correct/simplest algorithm was to add up the distance of all the pieces from the right with winning positions as odd and losing as even.

I thought up this proof for that.

Define: an "odd" position as one where the sum of the distances is odd and an "even" position as one where the sum of the distances is even.
1. The last move of any game (the * game) is to have a single piece on the board with distance of 1. In order to win, you must eventually end up in this position. This is an odd position.
2. If you are in an odd position, you can move your opponent into an even position: You can always move one piece to the right by one spot, decreasing the sum by 1, resulting in an even sum.
3. If you are in an even position, you cannot move your opponent into an even position: case 1) move one piece to the right, decreasing the sum by 1, resulting in an odd position. case 2) move one piece 3 to the right, decreasing the sum by 3, resulting in an odd position.
4. For optimal play, all winning initial positions are odd: since the * game is odd (1), you need to get to an odd position to win. If you're in an odd position, you can remain in an odd position (by 2 & 3). If you're in an even position, you cannot get into an odd position (by 2 & 3).
Re: Div2-500 proof (response to post by mcclosdl) | Reply
What is the explaination if two checkers are at odd positions and sum is even. The first player can use one of these odd positions to win? I don't really understood the editorial completely in the first place. Can you help me?
RSS