Stone Pile Redistribution Game

Game Theory · Hard · Free problem

You have two piles of stones containing $A$ and $B$ stones respectively, where $A$ and $B$ are positive integers. A move consists of:

  1. Choosing a positive integer $k$ such that both piles have at least $k$ stones.
  2. Removing $k$ stones from each pile.
  3. Placing all
k$ stones into exactly one of the two piles (your choice).

Note that the total number of stones is preserved. You repeat this operation until no legal move is possible (i.e., one pile is empty).

(a) Prove that the process always terminates.

(b) Characterize all initial pairs $(A, B)$ for which it is possible to end with one pile empty (i.e., all stones in one pile).

(c) Design an algorithm running in $O(\log(A + B))$ time that, given $(A, B)$, decides whether one pile can be emptied under optimal play and, if so, outputs a sequence of moves achieving this.

Hints

  1. What happens if you choose $k = \min(A, B)$? What do the piles look like after this move?
  2. After removing $\min(A,B)$ from each pile, one pile is empty and the other has $|A - B|$ stones. Where do you place the k$ returned stones?
  3. The one-move strategy always works: take $k = \min(A,B)$, drain the smaller pile to $0$, and dump all k$ stones into the larger pile. This gives $(0, A+B)$ immediately.

Worked Solution

How to Think About It: This is a combinatorial game theory problem with an invariant hiding underneath. The move "remove $k$ from each pile, add k$ to one pile" preserves the total $A + B$ but changes the split. The key question is: what quantity strictly decreases (guaranteeing termination), and what invariant determines reachability of the $(0, A+B)$ state?

Key Insight: Think in terms of binary representations. The move is intimately connected to the binary (base-2) structure of $A$ and $B$. Specifically, consider the "nim-value" or XOR-like properties of the pile sizes.

Part (a) - Termination:

The process always terminates because the player can force termination in a single move. Given piles $(A, B)$ with $A \le B$, choose $k = A$. After removing $A$ from each pile: $(0, B - A)$. Place the A$ stones into the second pile: $(0, B + A)$. The first pile is empty, and no legal move exists (any move requires both piles to have $\ge 1$ stone). Since the player can always choose to terminate, the process terminates whenever the player decides.

More generally, if we require that the process terminates for ANY sequence of legal moves (not just optimal), then we note the game state space is finite (pairs of non-negative integers summing to $S$), and since the player chooses $k$ and the target pile, they can always choose $k = \min(A,B)$ to terminate.

Part (b) - Characterization:

For any initial pair $(A, B)$ with $A, B \ge 1$, it is always possible to end with one pile empty. As shown above, choosing $k = \min(A,B)$ and placing the k$ stones into the pile that had the larger count achieves $(0, A+B)$ in a single move.

Therefore, the characterization is: every pair $(A, B)$ of positive integers allows ending with one pile empty.

Part (c) - Algorithm:

The algorithm is trivial given the characterization:

```python def solve(A, B): # Always possible. One move suffices. k = min(A, B) if A <= B: # Remove k=A from each, add 2A to pile 2 return True, [(k, 2)] # (k, pile_to_add) else: # Remove k=B from each, add 2B to pile 1 return True, [(k, 1)] ```

This runs in $O(1)$ time, which is certainly $O(\log(A + B))$.

However, if the problem intends a more restrictive move set (for example, if the k$ stones must go back to the pile they came from, or if there is some constraint I am missing), then the problem becomes significantly harder and likely involves binary representations, the Euclidean algorithm (explaining the $O(\log(A+B))$ complexity), and Nim-like game theory.

Alternative interpretation: if the player does NOT choose which pile receives the stones: If the k$ stones must go to a predetermined pile (say pile 1 always), then the move is $(A,B) \to (A+k, B-k)$ only. In this case, the analysis involves the GCD structure. Reachable states from $(A,B)$ under the constraint that the total $S = A + B$ is fixed are determined by divisibility. The state $(0, S)$ is reachable iff $\gcd(A, B) | S$, which is always true since $\gcd(A,B) | A$ and $\gcd(A,B) | B$ implies $\gcd(A,B) | (A+B) = S$. The $O(\log(A+B))$ algorithm would then mirror the Euclidean algorithm.

Answer: The process always terminates. Every pair $(A, B)$ of positive integers can reach the state $(0, A+B)$. A single move with $k = \min(A,B)$ suffices, giving an $O(1)$ algorithm.

Intuition

At first glance this looks like a deep combinatorial game theory problem, but the key realization simplifies everything: you can always terminate in one move. By choosing $k$ equal to the smaller pile size, you drain that pile completely, and then you place all the removed stones into the other pile. The total is conserved, and you end at $(0, A+B)$. The $O(\log(A+B))$ complexity hint in the problem suggests the intended version may have additional constraints (such as a fixed rule for where the k$ stones go, or restrictions on $k$), which would make the problem equivalent to running a Euclidean-algorithm-style reduction on the pile sizes. If you encounter this in an interview, the first thing to do is clarify the exact rules -- then check whether a greedy one-shot move works before diving into invariant analysis.

Open the full interactive solver →