Learn / Library / Brainteasers
Pair flips on a coin row
coins lie in a row. The coins in positions , , , , and show tails, and all the others show heads. One move picks neighbouring coins and flips both. What is the minimum number of moves needed to make all coins show heads?
Checking an answer needs JavaScript. The hint and the solution open without it.
Hint
Think of each tails coin as a token. A move can slide a token one place, remove neighbouring tokens, or create .
Solution
- Each move flips coins, so tails coins disappear in pairs, and a pair of tails at distance apart can be removed in moves (slide one tail along places and then remove both) but not in fewer.
- So the minimum is the cheapest way to pair up the tails by distance, and on a line the cheapest pairing joins neighbours in order.
- The tails at , and have distances , and , while any other pairing costs more (for instance , , costs ).
- The minimum number of moves is .
Answer: