🇳🇱
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
Solution
@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.
Solution
@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...
@freemo No. If you know they're all the same, you can just leave them for the remaining turns. Or if you got them all the same without realising it, you can flip them out, flip them back, whatever you like until your N turns are up. I'm just removing the assumption that the fact the game hasn't ended implies all four are not the same.