KA-0043Invariants and monovariants
5 points, difficulty 3 of 3Level 5–6about 165sA bag holds 5 black and 6 white stones. You repeatedly remove two stones: if they match you put a black one in, if they differ you put a white one in. What colour is the last stone?
Hints
Take them one at a time. The first gives nothing away.
1A nudge
Watch what happens to the number of white stones.
2The strategy
Check each kind of move and ask how the white count changes. If it only ever changes by an even amount, then whether it is odd or even can never change at all.
3The full solution
Two blacks: white count unchanged. Two whites: white count falls by 2. One of each: one white out, one white in, so unchanged. The white count starts at 6 and stays even, so the last stone cannot be white.
Solution
The reliable way
Track the number of white stones. Two blacks out and a black in leaves it unchanged. Two whites out and a black in lowers it by 2. One of each out and a white in removes one white and returns one, leaving it unchanged. Every move therefore changes the white count by 0 or by 2, so it stays even forever. It starts at 6, which is even, so the final single stone cannot be white - it is black. The transferable idea: find a quantity no move can change, and the ending is decided before you start.
The elegant way
The parity of the white count is invariant, so the answer depends only on whether the bag starts with an odd or even number of white stones - never on how you play.
Why this is on the test: Invariants turn an unbounded search into one observation, and this is the cleanest place for a student to meet the idea.