The last chip left in the bag

Question

A bag holds some red chips and some blue chips. You repeat the following move until one chip is left: reach in and take out two chips, then - if the two are the same color, drop them both and put one red chip into the bag; - if the two are different colors, drop them both and put one blue chip into the bag. Each move removes two chips and adds one back, so the bag shrinks by one each time and eventually a single chip remains. Predict the color of that final chip from the starting counts alone, and prove your prediction always holds, whatever order the chips happen to come out.

Accepted Answer

The final chip is blue exactly when the bag starts with an odd number of blue chips; otherwise it is red. The proof is a single invariant: the parity of the blue-chip count never changes. Check each type of move against the blue count. - Two blues (same color → add red): you remove 2 blue and add 0 blue, so blue drops by 2. Parity unchanged. - Two reds (same color → add red): no blue chips are involved at all. Blue count unchanged. Parity unchanged. - One red and one blue (different → add blue): you remove 1 blue and add 1 blue, a net change of 0. Parity unchanged. In every possible move, the…

The last chip left in the bag

Your answer

More Brainteasers questions