Last Ball Color

The Puzzle: In a bag, you have $W$ White balls and $B$ Black balls. You perform the following operation repeatedly until only one ball remains:

1. Pick two balls randomly.
2. If they are the Same color, discard them and put a Black ball back into the bag.
3. If they are Different colors, discard them and put a White ball back into the bag. What is the color of the last ball?

1. The Key Observation (The Invariant)

Let’s look at how the number of White balls ($W$) changes in each scenario:

• Pick 2 White: $W$ decreases by 2. (You remove 2 White, put back 1 Black).
• Pick 2 Black: $W$ remains the same. (You remove 2 Black, put back 1 Black).
• Pick 1 White, 1 Black: $W$ remains the same. (You remove 1 White and 1 Black, but put back 1 White).

Crucial Point: $W$ only ever decreases by 2 at a time. It never decreases by 1. This means the Parity (even or oddness) of the number of White balls never changes.

2. The Result

• If $W$ is Even (initially): The last ball must be Black.
• If $W$ is Odd (initially): The last ball must be White.

---

Interview-Focused Questions

Key Takeaway

This puzzle is a great example of an Invariant. In software engineering and algorithms, finding the property that never changes during a set of operations is often the key to proving correctness.