Minimum no. of coin flips (switch) needed so that all coins face the same side (Heads or Tails)

Question

Consider this, I have n coins and I have placed them in a random order (1st coin is Head, 2nd is Tails etc.). You do not know the order. You can flip one coin at a time and then I tell you if all the coins face the same side or not. You continue flipping until all coins are facing the same side.

I tried breaking it down to smaller base cases:
(1) when there is 1 coin: no need to flip
(2) when there are 2 coins: the only odd cases you can have are {H,T} or {T,H}, so flipping the first coin will do the trick
(3) when there are 3 coins: there are 6 odd cases you can end up, but 3 of them are similar to one another, hence only 3 cases to consider with {H,T,T}, {T,H,T} and {T,T,H} (same with one T and 2 heads). The strategy for this could be flipping the 1st coin, if the order is still not made then flip the second coin, if the order is still not made then flip the 1st coin again.

I am having a hard time coming up with a general algorithm for n coins. Any ideas?

Answer 1

Here is a general algorithm. The maximum number of flips needed is $2^{n-1}-1$.

Input: coin 0, coin 1, coin 2, ..., coin $n-1$

Procedure:
$\quad$ If all coins face the same side, return.

$\quad$ For $i$ from 1 to $2^{n-1}-1$ inclusive:
$\quad\quad$ If $i$ is divisible by $2^k$ but not $2^{k+1}$:
$\quad\quad\quad$ Flip coin $k$
$\quad\quad\quad$ If all coins face the same side, return.

---

For example, if there are no more than 8 coins, then just flip the coins at the following places successively as long as all faces do not face the same side.

0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0

Answer 2

Without going into the details, you are looking for something that's known as a Gray code. Any cyclic Gray code that has the all zero bitstring at the opposite part of the cycle as the all one bitstring gives a minimal expected solution time assuming an uniform random input.