Here is a algorithms/riddle i just solved that was kind of fun. So heres the setup. You have a circular table that spins with four evenly spaces opaque boxes on it around the outside. In each box is a coin that is either heads or tails. You get a maximum of 5 rounds, between each round you are blindfolded and the table ia spun randomly. During each round you can pick a box to open, look, the pick a second box to open and look. You can then flip none, any, or all, of the coins with open boxes. Then the boxes are closed before the next round. If at any point all four coins are the same then you win the game.

You must come up with a strategy that **guarantees** in 5 rounds or less that all 4 coins will be the same.

Tommorow i will take a picture of the flow chart i came up with the answer. In the meantime please give hints, answer, or thoughts in the comments but be sure to CW them. I will reply tomorrow with a picture of the answer and CW that as well. Good luck!

PS for a slightly harder version all the same rules apply except you need to pick both boxes to open simultaneously rather than one after thr other. With this harder version it is still possible in 5 rounds or less.

#riddle #algorithm #computerscience #programming #algorithms #puzzle

@freemo Here's the strategy I'd follow, compliant with the hard rules.

1st spin: Open two boxes diagonally opposite one another. Set both coins to heads.
2nd spin: Open two adjacent boxes. Set both coins to heads.
3rd spin: Open two diagonally opposite boxes. If one coin is tails, set it to heads and you win. If both coins are heads, set exactly one to tails and leave the other one heads.
4th spin: Open two adjacent boxes and flip both coins. If they were the same, you win.
5th spin: Open two diagonally opposite boxes. Flip both coins. You win.

Reasoning:
The first two moves guarantee that at least three of four coins are heads. If all four coins are heads, you've won, so we only have to worry about the case where exactly three are heads.
The third move either turns over the last remaining tails, in which case you win, or it leaves you with two adjacent heads and two adjacent tails.
The fourth move either turns over all the remaining heads, all the remaining tails, or one of each. In the first and second cases, you win; in the third case you are left with alternating heads and tails where you formerly had adjacent heads and adjacent tails.
The fifth move turns over all the remaining heads or all the remaining tails, depending on whether you happen to open the odds or the evens, so you win.

@khird
Yup you got it.

@freemo Let's extend the riddle by saying you have to set the coins the same after exactly N moves. You're allowed to have all four coins the same before then, but you won't win unless they're still the same (or again the same) at exactly N moves.

What's the smallest N for which there's a guaranteed winning strategy?

@khird hmm, let me ponder this...

@khird as far as i know the smallest N for a garunteed win is 5, you can sometimes win sooner but 5 is the smallest garunteed.

@freemo I don't believe you can guarantee a win in five without the instant-win condition in the original problem.

@khird hmmmm...

@khird so basically no way to verify when you won you're saying?

@freemo unless you can logically deduce from the the coins you've seen that it must be solved or must not be solved, you cannot make the assumption in either direction.

@khird without an oracle telling you that you've won i dont think its possible to do because of the random element.

@freemo proof of impossibility could be a solution to the puzzle 😎

@khird
Mathematically proving there is no solution to a conjecture is often itself an extremely hard task. That said i may be able to articulate why it isnt solvable if i give it some thought.

Any solution relies on first getting the coins to a state where you have 3 coins the same and the state of the 4th is unknown. The problem is i dont see how you can ever deduce the unknown state without an oracle since you can spin it as many times as you want and may always get the same choices every time. Flip it all you want and you can never find the unknown state without an oracle.

@khird
So proof of impossiblity is this.

Imagine you are so unlucky that every time you pick two cups, even if you alternate adjacent and opposite picks, you always keep picking the 2 out of the same 3 cups. In other words your so unlucky you never pick one specific cup.

No matter what you do the state of that one cup is always unknown to you and therefore you can never garuntee you will end any one round in a winning state.

@freemo exactly!

For similar reasons, even under the original instant-win rules, a version with five boxes is unsolvable. No matter how many times you open any arrangement of two boxes, fate can always allow there to be two boxes that don't match and you never see.

I think five boxes, opening three per turn, should work, but I haven't figured out what the target number of moves should be.

@khird
With 4 boxes you have two modes of selecting, adjacent or across, with 5 boxes you also have 2 modes of operation, adjacent or skip one, and you cant do opposite. But with 6 boxes you get 3 modes, adjacent, skip one, or across. I need to think about this some more but i suspect if a certain number of boxes is solvable depends on the number of modes. Compared to number of boxes. It may be (i need to ponder) that 6 boxes is solvable where 5 is not.