Basic Game Theory and Nim
In a finite impartial normal-play game, both players have the same legal moves from a position and the player unable to move loses. A position is winning if some move reaches a losing position, and losing if every legal move reaches a winning one. Nim is the classic solvable example: remove any positive number from one heap. The XOR of heap sizes determines the winner and constructs a winning move.
Prerequisites: Bitwise XOR; basic induction and optimal-play reasoning.
Build the idea
1. Establish the game assumptions
Normal play means taking the final object wins; misère Nim changes the rule and needs a different analysis. Moves change one heap only and strictly decrease total objects, so play terminates. The terminal all-zero position is losing. We assume optimal play by both players, not a random opponent.
2. Define the Nim-sum
Let S=h₁ XOR h₂ XOR … XOR hₙ. A position is losing exactly when S=0. If S=0, changing one heap from h to a different smaller h′ makes the new XOR h XOR h′, which is nonzero. Therefore no move from zero XOR stays at zero.
3. Construct a move from nonzero XOR
Take the highest set bit of S. Some heap h has that bit set. Set h′=h XOR S: its highest differing bit becomes zero, so h′<h and removing h−h′ is legal. New overall XOR is S XOR h XOR h′=0. These two directions prove zero positions lose and nonzero positions win by induction on the decreasing total.
4. Trace heaps 3,4,5
Their XOR is 3 XOR4 XOR5=2. Heap 3 can become 3 XOR2=1, so remove two objects from heap index 0. The remaining heaps [1,4,5] have XOR zero. There may be several winning moves; the program prints the first valid heap. When XOR is already zero, it prints LOSE and does not pretend there is a move that forces victory.
5. Introduce Sprague–Grundy carefully
For a terminating impartial normal-play game, assign each position the mex, the smallest nonnegative integer missing among its option Grundy values. Terminal value is zero. Independent game components, where each move changes exactly one component and leaves the others’ options unchanged, combine by XOR of their Grundy values. A Nim heap of size h has Grundy h. Arbitrary impartial games require computing these values first; XORing unrelated raw state numbers is not a valid general strategy.
C++17 implementation
This is a complete program. Compile with C++17 and enter the input described below.
// Key idea: 5. Introduce Sprague–Grundy carefully For a terminating impartial normal-play game, assign
// each position the mex, the smallest nonnegative integer missing among its option Grundy values.
#include<iostream>
#include<vector>
int main(){
int n;
std::cin>>n;
std::vector<unsigned long long>heap(n);
unsigned long long nimSum=0;
for(auto&h:heap){
std::cin>>h;
nimSum^=h;
}
if(nimSum==0){
std::cout<<"LOSE\n";
return 0;
}
for(int i=0;i<n;++i){
unsigned long long next=heap[i]^nimSum;
if(next<heap[i]){
std::cout<<"WIN\n"<<i<<' '<<next<<'\n';
return 0;
}
}
}
Complexity analysis
O(n) time for XOR plus a possible move scan, O(n) storage to retain heaps for constructing the move. Deciding the winner alone can stream in O(1) auxiliary space. Heap sizes are unsigned and at most 10^18, so bitwise operations remain within the type; no sum of all heap sizes is formed.
Example input and output
Read n (0..200000), then n heap sizes in 0..10^18. Under normal Nim print LOSE, or WIN and zero-based heap index plus its new size for one winning move.
Input
3 3 4 5
Output
WIN 0 1
Changing heap 0 from 3 to 1 makes 1 XOR4 XOR5=0.
Practical applications
Use for take-away heap games and as a starting point for impartial-game DP. For other finite games compute winning/losing states or Grundy values from legal transitions. Partisan, cyclic, scoring or simultaneous-move games need other theory.
Check your understanding
Why is h XOR S a legal reduced heap for some h when S≠0?
Put it into practice
Brute-force winning states for small heaps and compare with Nim-sum.
Show a hint
A state wins iff at least one smaller one-heap option loses.