Advanced Strategy — Wythoff, Flip, Palindrome & Beyond

You've mastered Nim. You know Grundy numbers. You can solve Stone Games in your sleep. Now it's time to level up. The problems in this article are the final bossof competitive programming game theory — the ones that separate "I know game theory" from "I understand game theory".

What makes these problems different?

• Wythoff's Game — The game that requires the golden ratio φ. Yes, you read that right. The Fibonacci sequence's cousin makes an appearance in a two-pile game.
• Flip Game II — A string-based impartial game where moves break the string into independent subgames. Classic Sprague-Grundy application with XOR of Grundy numbers.
• Palindrome Games — Remove palindromic subsequences. The "easy" version is a brainteaser; the "hard" version requires interval DP on palindrome structure.
• Cat & Mouse — A graph-based game with three possible outcomes: mouse win, cat win, or draw. Requires state-space BFS and backward induction.
• Even/Odd Strategy — Parity-based reasoning that often collapses to simple checks: count evens, check totals, pattern matching.

Problem: Two piles of stones. On each turn, a player can either: (a) remove any positive number of stones from one pile, OR (b) remove the same positive number of stones from both piles. The player who takes the last stone wins.

🔍 Real-Time Thinking — What Do I Know?

"OK, this is like Nim but with an extra move: remove equal from both. In standard Nim, the cold positions (P-positions) are when XOR of pile sizes = 0. But here, XOR doesn't tell the whole story because of the 'remove equal from both' move. Let me think about small positions..."

"For (0,0): it's terminal — no moves, losing position. Base case."

"For (1,0) or (0,1): can remove one stone from the non-zero pile → reaches (0,0). So (1,0) and (0,1) are winning."

"For (1,1): can remove one from both → reaches (0,0). So (1,1) is winning."

"For (1,2): Can remove 1 from pile A → (0,2). Can remove 1 from both → (0,1). Can remove 2 from pile B → (1,0). But wait... all these reach winning positions for the opponent? Let me check: (0,2) is winning (remove 2 from pile B), (0,1) is winning, (1,0) is winning. So (1,2) is LOSING! Found the first cold position!"

"Now (2,2): remove 2 from both → (0,0). That's a win. So (2,2) is winning."

"The cold positions follow a pattern: (1,2), (3,5), (4,7), (6,10), (8,13)... Wait — these involve the golden ratio! Let me check: aₖ = ⌊k·φ⌋, bₖ = aₖ + k where φ = (1+√5)/2."

The Betty Sequence Connection

Wythoff's Game is famous because its cold positions follow Betty sequencesinvolving the golden ratio φ = (1+√5)/2 ≈ 1.618:

• Lower Betty sequence: aₖ = ⌊k · φ⌋
• Upper Betty sequence: bₖ = ⌊k · φ²⌋ = ⌊k · (φ+1)⌋ = aₖ + k

These two sequences partition the natural numbers — every positive integer appears EXACTLY ONCE across both sequences! This is known as Beatty's theorem.

The Strategy

Given a position (a, b) with a ≤ b:

1. Let k = b - a (the difference between piles)
2. Compute aₖ = ⌊k · φ⌋ where φ = (1+√5)/2
3. If a == aₖ, this is a cold (losing) position → first player loses
4. Otherwise it's a hot (winning) position → first player can move to a cold position

Edge Cases

• a > b: Swap so a ≤ b first. The position (b, a) has the same status.
• a = 0, b = 0: Terminal cold position (k = 0, aₖ = 0).
• Large k: Compute ⌊k·φ⌋ carefully with floating point. φ = (1+√5)/2, use Math.floor(k * (1 + Math.sqrt(5)) / 2).
• Integer overflow: k·φ can be large. In C++, use int a_k = k * (1.0 + sqrt(5.0)) / 2.0;.

📋 Edge Cases to Consider

• Equal piles (a = b): k = 0, aₖ = 0. Cold only if both are 0. So any equal non-zero pile is winning (remove all from both).
• One empty pile: If a = 0 and b > 0, it's winning (remove b stones from the non-empty pile).
• Small positions: (1,2), (3,5), (4,7), (6,10) are cold. Everything else up to these values is hot.
• Precision: For k up to 10⁹, double precision is sufficient for the floor computation.

🤔 The Decision: Can I Reach a Cold Position?

"I'm at a hot position. I need exactly ONE move that reaches a cold position. I can either reduce one pile, or reduce both equally. The cold positions follow (aₖ, bₖ). So I need to check: can I reduce pile A to aₖ for some k, or reduce both to reach a cold (aₖ, bₖ)?"

This is the choose/not-choose decision: I choose to move to the cold position whose difference k = b - a, if a > aₖ I reduce pile A to aₖ; if a < aₖ I need a different move.

Problem: Given a string containing only '+' and '-'. Two players take turns flipping two consecutive '++' into '--'. The player who cannot make a move loses. Determine if the first player can force a win.

🔍 Real-Time Thinking — What Do I Know?

"This is an impartial combinatorial game. Each move flips two adjacent '+' to '--', which effectively splits the string into independent left and right segments. The '--' acts as a barrier — segments separated by already-flipped zones don't interact."

"Since this decomposes into independent subgames, I can use the Sprague-Grundy theorem: Grundy(entire game) = XOR of Grundy(each contiguous '++..+' segment). A position is winning iff Grundy ≠ 0."

"For a contiguous segment of '+' of length n, flipping at position i (0-indexed) breaks it into two segments: left has length i-1, right has length n-i-2. So Grundy(n) = mex of { Grundy(i-1) ⊕ Grundy(n-i-2) | for all valid i }."

The Sprague-Grundy Formulation

Let's derive this step by step:

1. A contiguous run of n '+' signs forms an impartial game.
2. Flipping positions [i, i+1] (0 ≤ i ≤ n-2) replaces the run of n with two runs: length i (left) and length n-i-2 (right).
3. The Grundy of the resulting position = Grundy(left) ⊕ Grundy(right).
4. Grundy(n) = mex{ Grundy(i) ⊕ Grundy(n-i-2) | 0 ≤ i ≤ n-2 }.
5. Base cases: Grundy(0) = Grundy(1) = 0 (no moves possible).

📋 Edge Cases to Consider

• No '+' at all: No moves possible. xorSum = 0. First player loses.
• Single '+' (n=1): No two consecutive '+' to flip. Grundy(1) = 0.
• String "++": Only one move. Grundy(2) = mex{0⊕0} = mex{0} = 1. Winning.
• String "++++": Grundy(4) = mex{G(0)⊕G(2), G(1)⊕G(1), G(2)⊕G(0)} = mex{0⊕1, 0⊕0, 1⊕0} = mex{1,0,1} = 2. Winning.
• Large maxN: Precompute Grundy up to n. The values become periodic after n=10 or so — use this for optimization.

🤔 The Decision: Which Flip Maximizes My Chances?

"I need to pick a flip such that the XOR of the resulting Grundy numbers is 0 (making it a losing position for my opponent). So I compute xorSum of all segments. I need to find a flip where: xorSum ⊕ Grundy(current) ⊕ Grundy(left) ⊕ Grundy(right) = 0. This is the choose/not-choose framework: I choose the flip that makes the total XOR zero."

Problem (Easy): Given a string s containing only 'a' characters, two players take turns removing a palindromic subsequence (not necessarily contiguous!). The player who cannot move (string is empty) loses. Who wins?

Problem (Hard): Same rules, but the string contains BOTH 'a' and 'b' characters. Who wins?

🔍 Real-Time Thinking — The Easy Version

"The string contains ONLY 'a's. A palindromic subsequence... wait, ANY subsequence of identical characters is a palindrome! 'aaa...a' is always a palindrome. So Alice can remove ALL characters in her first move (the entire string is a palindrome). She wins instantly unless the string is empty."

Answer (Easy): If s is empty → Bob wins. Otherwise → Alice wins (removes entire string in one move).

🔍 Real-Time Thinking — The Hard Version

"Now we have both 'a' and 'b'. Let's think..."

"If the entire string s is itself a palindrome, Alice can remove it all in one move and win. So the only interesting case is when s is NOT a palindrome."

"Bob's winning strategy: After Alice's first move, there are at most 2 distinct characters left (since only 'a' and 'b' exist). If the remaining characters are all the same → palindrome → Bob's turn → Bob removes all and wins. But wait..."

"Actually, there's a known result: For binary strings (only 'a' and 'b'), the second player (Bob) wins if and only if the string is NOT a palindrome and the string has an even number of characters? No — let me think more carefully."

The Actual Result

For the Palindrome Game with binary strings:

• If s is empty: First player loses (no moves).
• If s is a palindrome: First player wins (remove entire string).
• If s is NOT a palindrome:
  • If s contains only one character type → it's always a palindrome (all same chars). Contradiction — this case is covered above.
  • If s contains both 'a' and 'b' and is NOT a palindrome → Bob can ALWAYS win by optimal play.

Bob's Winning Strategy (when s is not a palindrome)

1. If Alice removes a set that leaves only one character type → palindrome → Bob removes all and wins.
2. If Alice leaves both character types, Bob can always mirror or counter to eventually leave a non-palindrome for Alice that she can't fully clear.
3. The key insight: with 2 character types, Bob can always force a win when the initial string is not a palindrome.

📋 Edge Cases to Consider

• Empty string: First player loses regardless.
• Single character: Always a palindrome → first player wins.
• All same characters: Palindrome → first player wins.
• Two characters, alternating like "ab": Not a palindrome → Bob wins.
• "aba": Palindrome → Alice wins (remove all).
• "aab": Not a palindrome → Bob wins.

The DP Approach for Hard Version

For the interval DP solution on Palindrome Game Hard, we compute dp[l][r] = whether the current player can force a win on substring s[l..r]:

Problem: You are given a directed graph. The mouse starts at node 1, the cat at node 2. Node 0 is a safe node (the mouse wins if it reaches 0). The mouse moves first. Players alternate moving along edges. The cat wins if it catches the mouse (same node). The game may go on forever (draw). Determine the outcome.

🔍 Real-Time Thinking — What Do I Know?

"This is a partisan game on a graph — but actually it's impartial because both players have the same move options (follow edges). The twist is: there are THREE possible outcomes (mouse win, cat win, draw), not just two!"

"I can model this as a state space graph where each state is (mousePos, catPos, turn). The game has at most n × n × 2 states (where turn = 0 for mouse, 1 for cat). For n ≤ 50, that's at most 5000 states — manageable for BFS/DP."

"Terminal states: Mouse wins if mousePos = 0 (safe node). Cat wins if mousePos = catPos."

The Algorithm: Backward Induction with BFS

We use a technique called retrograde analysis (backward induction):

1. Initialize all states as unknown.
2. Mark winning states: mousePos = 0 → MOUSE WIN; mousePos = catPos → CAT WIN.
3. Use a queue to propagate: when a state is determined, its predecessors may become determined too.
4. Mouse's turn: If ANY move leads to MOUSE WIN → state is MOUSE WIN. If ALL moves lead to CAT WIN → state is CAT WIN.
5. Cat's turn: If ANY move leads to CAT WIN → state is CAT WIN. If ALL moves lead to MOUSE WIN → state is MOUSE WIN.
6. States that remain unknown after propagation are DRAW (cycle forever).

📋 Edge Cases to Consider

• Mouse starts at safe node (0): Immediate MOUSE WIN. No moves needed.
• Cat starts at same node as mouse: Immediate CAT WIN.
• No edges from a node: If mouse is at a dead end and not safe, it can't move. If cat is at a dead end, it can't move.
• Graph has cycles: The algorithm correctly detects draws from states that can't be resolved.
• Disconnected graph: Cat may never reach the mouse → potential draw.

🤔 The Decision: Minimax on the State Graph

"On my turn, I evaluate all my possible moves. If I'm the mouse, I choose a move that leads to MOUSE WIN (if one exists). If I'm the cat, I choose a move that leads to CAT WIN (if one exists). This is pure minimax on the state graph — the choose/not-choose framework extended to three outcomes."

Problem: Two players have RPG characters with stats (attack, defense, health, mana, etc.). On each turn, a player can perform an action (attack, heal, buff, etc.) that changes the game state. Determine the winner under optimal play.

🔍 Real-Time Thinking — What Do I Know?

"This is another state space game like Cat & Mouse. Each game state is defined by (player1HP, player2HP, cooldowns, mana, etc.). But the state space can be huge! I need to find patterns or reduce dimensions."

"Key observation: Many RPG game states have a limited number of meaningful actions. If I can bound the total number of states (e.g., total HP ≤ 1000, mana ≤ 100), I can use DP/memoization on the state space. The minimax rule applies: I choose the action that maximizes my winning chance, assuming my opponent minimizes it."

State Space Reduction

• Identify invariant properties: Some stats may be bounded or monotonic (HP only decreases).
• Symmetry reduction: Many states are symmetric — prune by canonical representation.
• Turn parity: If the total number of possible actions is limited, the game must end within some bound.

Problem: There are n points arranged in a circle. Two players take turns connecting two adjacent unconnected points with an edge. The player who completes a triangle wins (or loses, depending on variant). Determine the winner.

🔍 Real-Time Thinking — What Do I Know?

"This is a positional game on a cycle. Symmetry often plays a key role. If n is odd, the first player can use a strategy stealing argument: mirror the opponent's move across the center. If n is even, the second player might have a symmetric strategy."

Key Insight: Symmetry

For the circle game (and many symmetric board games), the strategy-stealing argumentoften proves the first player can always win — but it doesn't tell us HOW. For specific variants:

• Odd number of points: First player picks a point, then mirrors opponent's moves across the diameter through that point.
• Even number of points: Second player can mirror across the center if the first player's move was not central.
• Triangle completion loses: Avoid creating a path of length 2 where the third edge would complete a triangle.

Many game theory problems reduce to simple parity (even/odd) checks orcounting patterns. These are the "hidden gem" patterns that experienced competitive programmers spot immediately.

Even Number Addicts

Problem: There are n numbers. Two players take turns picking numbers. Alice wants the sum of her numbers to be even. Bob wants the sum of his numbers to be even too (or Alice says "I can make my sum even" at the end). Determine who wins under optimal play.

🔍 Real-Time Thinking — What Do I Know?

"Parity! I don't care about the exact values — only whether each number is even or odd. Even numbers don't change the sum parity. Odd numbers flip it. So this is about controlling the number of odd numbers each player ends up with."

The Solution

Let's denote:

• evens = count of even numbers
• odds = count of odd numbers

📋 Edge Cases to Consider

• All evens: Alice's sum is always even regardless of picks → Alice wins.
• All odds, n is odd: Alice gets ceil(n/2) odds, which is odd → sum is odd → Alice loses if she needs even.
• Mixed evens and odds: Alice can use evens strategically to skip picking odds.

Nullify Matrix

Problem: Given an m×n binary matrix, two players take turns. On your turn, you pick a row or column that has at least one 1 and nullify it (set all its elements to 0). The player who cannot move loses. Determine who wins.

🔍 Real-Time Thinking — What Do I Know?

"This is a Nim-like impartial game where each move removes a set of 1's. But there's a crucial observation: picking a row nullifies that entire row, and picking a column nullifies that entire column. This is equivalent to the game of Dawson's Kaylesor turning-turtles on a matrix. But actually — there's a simpler view: each 1 is a token, and a move removes all tokens in a row or column. This is isomorphic to the game of Dawson's Kayles only if we consider that overlapping rows/columns interact."

"Key insight: The game is equivalent to having two piles (rows and columns). Each move picks either a row or column that still has a 1. But actually, it reduces to: if there's at least one 1 in the matrix, the first player usually wins because they can pick the row or column with the most 1's. But the optimal play is deeper..."

Substring Removal Game

Problem: Given a string s, two players take turns removing a substring that satisfies some property (e.g., all characters same, palindrome, balanced, etc.). The player who cannot move loses. Determine the winner.

🔍 Real-Time Thinking — What Do I Know?

"This combines interval DP with game theory. Each move removes a contiguous substring, splitting the remaining string into left and right parts. The Grundy of a segment = mex of { Grundy(left) ⊕ Grundy(right) | for each valid substring removal }."

📋 Edge Cases to Consider

• No valid substring: Grundy = 0. First player loses.
• Entire string is valid: First player removes entire string → wins.
• Only single-character removals: Game degrades to normal-play on n elements, which has Grundy = n mod 2.
• All substrings valid: First player removes everything in one move → wins.

1. Wythoff's Game uses the golden ratio φ = (1+√5)/2 for Betty sequences: aₖ = ⌊k·φ⌋, bₖ = aₖ + k. Cold positions partition the naturals.
2. Flip Game II applies Sprague-Grundy to strings: flipping '++' splits the string into independent subgames. Grundy(n) = mex of XOR pairs from splits.
3. Palindrome Game Easy is trivial: single character type → first player removes entire string at once. Always wins if non-empty.
4. Palindrome Game Hard with binary strings: palindrome → first player wins. Not palindrome → second player wins (using optimal counter-strategy).
5. Cat & Mouse transforms a graph game into a (mousePos, catPos, turn) state space with BFS backward induction. Three outcomes: mouse win, cat win, draw.
6. World of Darkraft extends state space to RPG stats. Use memoization on bounded state dimensions. Watch for exponential explosion!
7. Circle Game uses symmetry: strategy stealing or mirror strategies often determine the winner based on parity of n.
8. Even Number Addicts reduces to counting evens and odds. Only parity matters, not actual values.
9. Nullify Matrix is isomorphic to a bipartite graph game. Use Grundy numbers on row/column connections.
10. Substring Removal Game is interval DP + Grundy: dp[l][r] = mex{ dp[l][i-1] ⊕ dp[j+1][r] for each valid substring [i,j] within [l,r] }.

Here's every problem covered in this article. Open each in the playground, implement the solution, and verify against the test cases. Start with the easier ones (Wythoff's, Flip Game II) and work up to the hard ones (Cat & Mouse, Nullify Matrix).