🇳🇱
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...
@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.
@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.
@freemo some further observations:
For any number of boxes:
If you're allowed to choose all the boxes, a win is trivially possible: flip all to heads.
If you're allowed to choose all but one of the boxes, a win is trivially possible: flip all to heads; if you then see a tails turn it to heads, if not turn all coins to tails.
For five boxes:
There's no solution with three choices, because there's no penultimate state from which you can guarantee that you'll choose all the remaining heads or all the remaining tails. So five boxes has only the trivial solutions.
For six boxes:
I have a solution for four choices in five moves, which may not be optimal (I haven't searched exhaustively for other strategies).
The number of patterns for given numbers of boxes and choices is from the OEIS: https://oeis.org/A047996, under "example". I don't understand the notation they use for the generating formula, but they call it a "circular binomial coefficient" which makes sense.
@khird I actually created a notation/process where you can determine if a configuration is solvable. I didnt have a chance to try it out on various combos. Works like this.
Represent selection modes with binary numbers. So selecting one out of 4 boxes might look like 0001, 2 selected out of 4 would be 0011 or 0101.
To see if two selection modes are equivalent reduce them to what im calling "standard form". What that means is you left or right shift the binary number (taking any digits that roll off and replacing it on the other end) and do this until the number is in its smallest representation. So 1010 would have a standard form of 0101 (most significant digits on the left). If the standard form of two selection modes are the same then they are equivelant.
Next compute all possible selection modes in standard form for the given parameters. For the original puzzle this would be:
0011
0101
No other selection modes are possible.
Next do an OR operation on all possible selection modes, here we get:
0111
If the resulting binary number has one or fewer 0s then a solution is possible. If it has greater then a solution is impossible.
@freemo You're half right. Your test is necessary but not sufficient, so it'll sometimes answer "possible" when there isn't really a solution.
For example, five boxes three choices. Your selection modes are:
00111
01011
Their bitwise union is:
01111
which has a single zero, so by your algorithm it should be solvable. But in fact it isn't. If it were, you'd have a nearly-solved state, where, no matter how the table was spun, you'd be able to guarantee you either get *all* the remaining heads or *all* the remaining tails.
There's another failure mode too in that "standard form" isn't necessarily the worst-case form. Consider six boxes three choices:
000111
001011
001101
010101
Their bitwise union is 011111. But if we rewrite the selection modes, rotating the second and third ones, as
000111
010110
010011
010101
then we get a bitwise union of 010111 which is clearly unsolvable.
hmm yes you may be right, this is why i should have worked through some examples first... well at least i got a notation to start with.
So thinking about this some more, I thibnk my approach actually does work. **But** only for the easier case where the selections are allowed to be made sequentially rather than simultaneously.
I ran through the 5 case select 3 example and can solve it using sequential selection but impossible with simultaneous selection
@freemo Could you please type up your strategy? I haven't really looked at the sequential choice version, but it might offer clues to solving the general case.
Never mind, i take that back too (I have a cold and clearly im not thinking straight :) )
@khird hmm.. there is also the case where you can flip some number of coins but it doesnt have to be the coins you revealed (if you flip a coin not revealed you dont get to know the new or old state)... but that might be too easy
@freemo Oh man, hope you feel better soon!
I just spent a bit looking at the sequential case and I think I've proved it's impossible. Obviously the penultimate state can't have four heads or four tails, because then you're just hoping that by luck you happen to get the odd one out. So it's got to be a three-two split, of which there are two types.
Your first choice is completely blind, so it's possible you choose one of the majority (which I've labelled black in the diagram, but could be heads or tails). Let's stipulate that's the case, so there's no new information gained after the first move and we can predetermine the second move. If you flip a second black coin, you have to know exactly where the third black coin is to guarantee a win. If you flip a white coin, you have to know exactly where the second white coin is to guarantee a win. But in either case, if you draw one of the pairs shown in the diagrams, there are two possible orientations of the board - you know you're on one of the lines of a certain colour, but not which, and consequently not where the final piece you need is.
@khird Yea I agree the sequential case for 5 is impossible.. the key is that you need to maneuver into a state where only the last step you can select all of the same oriented coins in a garunteed way. That cant happen in any arrangements. So yea I agree with yoru analysis here.
@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 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.