Marble Parity Puzzle
A bucket contains an odd number of white marbles and some number of black marbles. Outside the bucket you have an unlimited supply of black marbles. You repeat the following procedure:
- Randomly pick 2 marbles from the bucket.
- If at least one of them is black, discard one black marble (put it outside) and return the other marble to the bucket.
- If both are white, remove them both and place one black marble into the bucket.
Each step reduces the total count in the bucket by exactly one. Eventually only a single marble remains.
What color is the last marble?
Hints
- Don't try to simulate the process. Instead, look for a quantity that is conserved (or whose parity is conserved) across every possible step.
- Track the number of white marbles $W$ separately. Check each of the three cases (two blacks, one of each, two whites) and see how $W$ changes.
- In every case, $W$ changes by $0$ or $-2$. Since $W$ starts odd, it stays odd -- and odd means $W \geq 1$, so the last marble standing must be white.
Worked Solution
How to Think About It: Whenever you see a process that removes items according to color-based rules, your first instinct should be: track the parity of each color separately. The total count drops by 1 every step, so the process definitely terminates with one marble. The question is whether that survivor can be pinned down. Instead of simulating, ask: is there an invariant -- some quantity that never changes -- that forces the answer?
Quick Estimate: Think about a tiny example. Start with 1 white and 2 black marbles. Step 1: pick two marbles. If you pick 2 blacks, discard one black, put the other back -- you have 1 white, 1 black. Step 2: pick the white and black, discard the black, put the white back. Last marble: white. Try 3 whites, 0 blacks. Step 1: pick 2 whites, remove both, add 1 black -- now 1 white, 1 black. Step 2: pick white and black, discard black, keep white. Last marble: white again. Every small case gives white.
Approach: Track the parity of the white marble count through each case.
Formal Solution:
Let $W$ be the number of white marbles in the bucket. We examine how $W$ changes in each case:
- Two blacks drawn: One black is discarded, one goes back. $W$ is unchanged. Total drops by 1.
- One black, one white drawn: The black is discarded, the white goes back. $W$ is unchanged. Total drops by 1.
- Two whites drawn: Both whites are removed and one black is added. $W$ decreases by 2. Total drops by 1.
In every case, $W$ changes by either $0$ or $-2$ -- always an even number. This means the parity of $W$ is an invariant of the process.
We start with $W$ odd. Therefore $W$ is odd after every step. In particular, $W$ can never equal $0$, because $0$ is even.
Since the total marble count decreases by 1 per step, we eventually reach exactly 1 marble. At that point $W \geq 1$ (it cannot be zero), but there is only 1 marble total, so $W = 1$. That marble is white.
$$\boxed{\text{The last marble is white.}}$$
Answer: The last marble is always white. The parity of the white count is invariant -- it starts odd and can only change by an even number, so it stays odd forever and can never reach zero.
Intuition
This is a classic parity invariant problem. The whole trick is that the rules are rigged so white marbles can only disappear in pairs. That means the white count flips between odd values -- it can never cross the even/odd boundary. Once you see that, the answer is forced: you started with an odd number of whites, and zero is even, so you can never run out of white marbles. The last marble must be white regardless of how many blacks you started with or the order in which marbles are drawn.
Parity invariants show up constantly in combinatorics puzzles and in quant interviews. The meta-lesson: when a process has complicated branching, don't try to track everything. Find a single quantity whose behavior is simple (here, parity is locked) and use it to constrain the outcome. This is the same style of reasoning you use when you notice that a portfolio's delta is always positive, or that a martingale can never cross certain boundaries -- reduce the problem to one clean invariant and let it do the work.