Convert a series of 0s and 1s into another series where it only consists of 1s or only consists of 0s

Question

Ali Baba is trying to enter a cave. At the entrance, there is a drum with four openings, in each of which there is a pot with a herring inside. The herring may be lying with its tail up or down. Ali Baba can put his hands into any two openings, feel the herrings, and put any one or both of them either tail up or tail down as he pleases. After this, the drum rotates and once it stops, Ali Baba cannot determine into which openings he put his hands before. The door to the cave will open as soon as the four herrings are either all tail up or tail down. What should Ali Baba do?
This question is similar to a "binary" question, where I have to convert a series of 1s (up) and 0s (down) into all 1s or 0s, but I am not sure how to do that here with randomization.

Answer 1

So lulu's link can be adapted to solve this problem in $7$ moves, flipping herrings in either adjacent or opposite openings.

The initial state is either 2 tail-up ($U$) and 2 tail-down ($D$) $=2U+2D$, or $3U + D$ or $U+3D$.

If we have $2U+2D$, flipping opposite herrings will either open the door or maintain a state where the similar herrings are adjacent. Flipping adjacent herrings will convert similar adjacent herrings to either a win or to similar diagonal herrings. So in this case, flipping opposite-adjacent-opposite will encounter a winning state.

Flipping any two herrings will convert $3U + D$ and $U+3D$ into one of those two states. Flipping a single herring will convert both $3U + D$ and $U+3D$ into either a winning state or $2U+2D$.

So opposite-adjacent-opposite-single-opposite-adjacent-opposite is a sequence of seven moves that will open the door (at some point). No inspection of herrings required in this - you just flip them, whatever the state.

Answer 2

When inspection is allowed (as described in the post) one can open the door in maximum 5 steps: Two opening that are next to each other will be addressed as a N-pair, and two openings that are opposite to each other will be addressed as a O-pair. Now just follow the steps below:

1. Choose any N-pair and put both tail up.
2. Choose any O-pair and put both tail up. If the door still had not opened, there must be three tails up and one down.
3. Choose any O-pair. If one of them is tail down, flip it and you are done. Otherwise both are tail up, just flip one of them. Now you have a N-pair with tail down and a N-pair with tail up.
4. Choose any N-pair and flip both. If both tails were in the same direction you are done. Otherwise you have a O-pair with tail up and a O-pair with tail down.
5. Choose any O-pair and flip it.

Now all tails are in the same direction - Enter the cave.