What is the minimum number of groups of three coins you can flip in order to flip every coin so that it is heads-down?

Question

Question: Suppose that there are seven coins arranged in a circle. Every coin is heads-up. Your goal is to flip every coin so that it is heads-up. You may, however, only flip groups of three adjacent coins. You may flip any such group of three coins, and you map flip as many such groups as you choose, one group at a time. What is the minimum number of groups of three coins you can flip in order to flip every coin so that it is heads-down?

My attempt:

Let $x$ be the number of groups to be flipped. So we can interpret the question as $$3x≡0 \,\,\,mod \,\,\,7.$$ One possible solution is $x=7$. So it requires at most 7 groups. On the other hand, clearly it requires at least $3$ groups. So minimum is between $3$ and $7$.

Then I am stuck here.

Any hint is appreciated.

Answer 1

HINT, as requested.

I don't think doing things mod $7$ helps. Instead I would do it mod $2$, to represent the fact that if you flip the same coin twice, that is equivalent to doing nothing. Since you want to flip every coin from Heads to Tails, any solution with $x$ moves (i.e. flipping $x$ groups) must satisfy:

$$3x \equiv 7 \pmod 2$$

This of course just means $x$ must be odd. Now you need to analyze case by case:

• $x=1$ is insufficient.

• $x=3$ is insufficient. (I'd say this is obvious, but if you really want a rigorous proof, then do a case analysis by whether the first $2$ groups overlap by $0, 1, 2$ or $3$ coins.)

• $x=5$ is insufficient. This is the hardest case to analyse but there is a good trick. Hint: look at the complement / see the next bullet.

• $x=7$ is sufficient. You need to prove this by construction.

All of the above together would prove that minimum $x=7$.

Can you finish from here, or do you need more hints?

Answer 2

Label the coins $a$ to $g$, and the groups of three coins $A$ to $G$ where the label corresponds to the middle coin.

Flipping the same group twice is equivalent to doing nothing, so we flip each group either $0$ or $1$ times.

Each coin must be flipped an odd number of times. Suppose wlog that coin $a$ is flipped only once. What can we say about the number of times that $g$ and $b$ are flipped?