CAT 2021 Slot 1 Mock: Game Theory Problem and Solution
Problem Statement:
Three players (A, B, C) take turns picking 1, 2, or 3 stones from a pile of 10 stones. The player who picks the last stone wins. Player A goes first. Determine if Player A has a winning strategy and explain it.
Solution:
Step 1: Understand the Winning Condition
The game ends when all stones are taken. The player who takes the last stone wins. This is a classic take-away game with a forced strategy based on modular arithmetic.
Step 2: Identify "Key Numbers" (Critical States)
If a player leaves the opponent with 4 stones, the opponent cannot win:
If opponent takes 1, you take 3 (total 4).
If opponent takes 2, you take 2.
If opponent takes 3, you take 1.
You win by taking the last stone. Thus, 4 stones is a losing position.
Step 3: Generalize the Pattern
The losing positions repeat every 4 stones:
4, 8, 12, ...
If a player leaves the opponent at these numbers, they are guaranteed to lose.
Step 4: Apply to the Given Problem (10 Stones)
Player A’s goal is to leave Player B with 8 stones (a losing position).
To do this, A takes 2 stones first (10 – 2 = 8).
Step 5: Strategy Execution
A takes 2 stones → 8 left.
B’s turn: Whatever B takes (1-3), A takes (4 – B’s move) to leave 4 stones.
Example:
B takes 1 → A takes 3 (8 → 4).
B takes 2 → A takes 2.
B takes 3 → A takes 1.
A forces B to 4 stones, then repeats the strategy to win.
Step 6: Conclusion
Player A can always win by reducing the pile to 8 stones first and maintaining the 4-stone gap. This is a winning strategy.
Final Answer:
Player A has a winning strategy. By initially taking 2 stones to leave 8, A can force B into losing positions (4, 0) through complementary moves.
Formula Application:
Key Insight: Losing positions = (4k) (where (k) is a positive integer).
For (n = 10), the nearest losing position is (8 = 4 \times 2).
English Explanation:
The solution leverages modular arithmetic to identify losing positions. Player A’s first move (2 stones) ensures B faces a losing state, allowing A to control the game flow.
Let me know if you need further clarification or additional problems! 🎯
|
