2
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ If everytime we flip a coin in the above algorithm, we also print out the array of coins except the last coin which is never flipped , we will get $(n-1)$-bit Grey code. That is, in fact, how the above algorithm is made. $\endgroup$
    – John L.
    Commented Feb 8, 2020 at 17:35
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.