🇳🇱
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
@lefarfadet it says "randomly" which i took to mean it can stay the same or turn 90 degrees clockwise, 90 degrees anticlockwise, or 180 degrees around, but you don't know because you were blindfolded while it was spinning.
@khird
That is a correct interpretation of the rules.
@lefarfadet
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...
@khird do you have to make a flip every turn?
@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.
@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.
@freemo only opening two boxes per turn, you can't do five or six. I think there might be a solution if you allow the player to open three per turn, at least for five.
For five boxes, choosing two: whenever you choose adjacent, suppose you choose boxes one and two; whenever you choose skip-one, suppose you choose one and three. Box four contains a heads, and box five contains a tails. You'll never be able to get all five the same.
For six, choosing two: suppose your adjacent choices are one and two, your skip-one are one and three, and your opposite are one and four. You'll never be able to get five to match six.
@khird
I think if you select 3 you can solve 5 or 6 boxes, you dont need 4 to solve 6 just 3. So its not number of boxes minus 2.
@freemo I don't think three flips solves six boxes. Your patterns are 1-2-3, 1-2-5, 1-3-5, 2-3-5, unless I'm forgetting one. If box four doesn't match box six you're out of luck.
@khird
Ill work through my logic on 6 boxes tomorrow. I think i see how to solve it but i need to get it on paper, see if there is a hole in my logic. Also will be helpful to nail down a workable notation.
@khird
So new problem, given a certain number of boxes, and a number of flips per round, how can we determine if it is solvable, and the number of rounds needed to garuntee a solve, assuming an oracle.
@freemo jumping right to the general case!
I think it's going to be exponential difficulty in at least flips-per-round, and probably also in boxes.
My algorithm is this:
Go through all known cases: if I were told the state of the boxes, for each pattern I could choose, what possible combinations would I find?
For each state-choice-combination triplet, and each possible combination I could set the coins to, what state (or superposition of states) could I leave it in?
Go through the unknown states the same way, by superposing the known ones, building all the way up to completely unknown (all states possible).
Make the decision tree by minmaxing, like in two-player game theory. If the starting state of "completely unknown" has a path to either all-heads or all-tails, count the steps in the path. If there isn't a path linking the starting state to the winning states, it's unsolvable.
@freemo I'm not really understanding this setup. So there's a round table, with 4 boxes on them in cardinal directions, let's say. Each box contains a coin.
5 times the table is spun randomly, you dunno since you're blindfolded. Then when a spin's done, you can open the box closest to you to check the status of the coin. You can decide to put it heads or tails.
So that's 5 times you can do this, no clue if it's the same coin or not since it was random without you being able to observe it.
Then you have to come up with a strategy that guarantees in 5 rounds or less that all 4 coins will be the same facing? Is that another 5 rounds, or is that this one 5 rounds?
@trinsec
There is only a single set of 5 rounds. You can check and flip up to 2 coins each round.
@freemo Oh, and it can be any 2 coins, not any nearest to you or something? You just don't know which ones were north south etc before?
@trinsec
Right it can be any 2 coins but you have no idea what coins were which in the roevious round since the table is spun
@freemo
Does the table spin always in the same direction, say clockwise for example ?