Maths Olympiad Prep

Library / /232 of 377

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:

Eight coins are arranged in a circle heads up. A move consists of flipping over two adjacent coins. How many different sequences of six moves leave the coins alternating heads up and tails up?

Solution

Solution:

Imagine we flip over two adjacent coins by pushing a button halfway between them. Then the outcome depends only on the parities of the number of times that each button is pushed. To flip any coin, we must push the two buttons adjacent to that coin a total of an odd number of times. To flip every other coin, the parities must then progress around the circle as even, even, odd, odd, even, even, odd, odd. There are 4 ways to assign these parities. If we assume each button is pressed either once or not at all, this accounts for only four presses, so some button is also pressed twice more. Suppose this button was already pushed once. There are 4 of these, and the number of possible sequences of presses is then 6!/3!=1206!/ 3! = 120. Suppose it has not already been pressed. There are 4 of these as well, and the number of possible sequences is 6!/2!=3606!/ 2! = 360. The total number of sequences is then 4(4120+4360)=76804(4 \cdot 120 + 4 \cdot 360) = 7680.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.