### Joy of Problem Solving

Above are shown three coins, each with one gold side and one silver side. Is it possible to successively flip over pairs of adjacent coins so that all 3 coins are gold side up?

Note: "Flip" indicates switching from gold to silver or back again, not a random flip as in probability. "Pairs of adjacent coins" means only two coins next to each other may be flipped at a time.

# Flipping Pairs

For the above arrangement, is it possible to successively flip over pairs of adjacent coins so that all of the coins have their gold sides facing up?

Note: "Flip" indicates switching from gold to silver or back again, not a random flip as in probability. "Pairs of adjacent coins" means only two coins next to each other may be flipped at a time.

# Flipping Pairs

There are 8 possible initial arrangements with 3 coins. In how many of these 8 arrangements is it possible to flip over pairs of adjacent coins so that all of the coins have their gold sides facing up? (Note: click on the coins above to flip them over).

# Flipping Pairs

Each of the arrangements of three coins which we were able to flip into all gold coins had an odd number of gold coins (1 or 3). Like most patterns in problem solving, this is no coincidence.

Each flip of adjacent coins does one of the following:

• increases the number of gold coins by 2 (if both coins were silver);
• decreases the number of gold coins by 2 (if both coins were gold);
• leaves the number of gold coins unchanged (if one was silver and one was gold).

In every case, the parity (even or odd) of the number of gold coins does not change. For all three coins to be gold, it is necessary that the original number of gold coins is odd as well.

# Flipping Pairs

Is it possible to flip over pairs of adjacent coins so that all of the coins have their gold sides facing up?

# Flipping Pairs

You are given an initial arrangement that has 100 coins, 99 of which are gold side up. Is it possible to successively flip over pairs of adjacent coins so that all of the coins have their gold sides facing up?

# Flipping Pairs

We built up from small cases to discover an interesting property of the coin flipping problem. Specifically, it is necessary that the parity of the initial number of gold coins is the same as the parity of the total number of gold coins in order to be able to make all of the coins gold.

It turns out that this condition is sufficient. For example, if there is an even number of coins and you start with any even number of gold coins, it is always possible to make all of the coins gold. Later in this course, we'll explore an algorithm for doing so.

×