Cards on a Square Turntable
Source: Steve Miller's Math Riddles
Problem:
A square has a quarter in each corner. You are blindfolded and must get all quarters to be heads up or all to be tails up. You will be told when you have done this. You may flip however many you want, then ask if you are done (this constitutes a turn). The square is then rotated/spun an undisclosed number of times. You then get another turn and so on…
Is there a strategy that is guaranteed to work in a finite number of moves, and if so, what is that smallest number of moves you need to be 100% you’ll be able to have all heads up or all tails up?
Problem:
A square has a quarter in each corner. You are blindfolded and must get all quarters to be heads up or all to be tails up. You will be told when you have done this. You may flip however many you want, then ask if you are done (this constitutes a turn). The square is then rotated/spun an undisclosed number of times. You then get another turn and so on…
Is there a strategy that is guaranteed to work in a finite number of moves, and if so, what is that smallest number of moves you need to be 100% you’ll be able to have all heads up or all tails up?
The same problem is there on the blog - in a different form - asked more than 50 months back :-) - Blind Flipping - CSE Blog
Following strategy assures all heads or all tails on all corners of the square in 8 turns:
ReplyDeleteNomenclature used:
1. Head is 1 and tail is 0
2. 'X-flip' implies flipping both coins on any one diagonal of square
3. 'side-flip' implies flipping both coins on any one side of the square
4. 'Corner' implies flipping 1 coin on any of the corners
Strategy:
There are 4 possible arrangements( Rotation is irrelevant, 0 and 1 can be interchanged):
A. 1 1 (Target) B. 1 0(Sides) C 1 1(L Shape) D 1 0(X Shape)
1 1 1 0 1 0 0 1
Move 1: Ask for a turn ( Game ends of starting position is Target, A option is closed)
Move 2: Do an X-flip, Ask for a turn( Game ends if starting position is X-shape, D option is closed)
Possible States after Move 2:
For B('sides'), we get 'sides' arrangement only
For C ('L-shape), we get 'L-shape' only( Change from three 1s to three 0s does not matter)
Move 3: Do a side flip, ask for a turn
Possible states after move 3:
For B, we get Target(game over) or X-shape
For C, we still get 'X-shape'
Turn 4: Do an 'X-flip', ask for a turn
For B option left: we get target (game over, B is done)
For C option: we still have an L-shape
Now, only option C is left with an L-shape
Turn 5: Flip one corner coin, we will get
1. X-shape or
2. 'Sides' or
3. Target (game ends)
Turn 6: Do an X-flip, ask for a turn
We get:
1. Target (Game ends) or
2. 'Sides'
Turn 7: Do a side flip, ask for a turn
We get:
1. Target (game ends) or
2. X-shape
Turn 8: Do an X-flip, ask for a turn
GAME ENDS!
Minimum moves:
Above strategy ensures no additional options are generated while we work on closing one option. However, while closing one option, other options aren't resolved.
I tried having parallel resolution of 2 or more options but couldn't find a better solution.
Solution here: http://www.cseblog.com/2009/11/blind-flipping.html
DeleteClarification on arrangements:
ReplyDeleteEach number represents coin-face on one corner of Square
A(Target):
1 1
1 1
B(Sides):
1 0
1 0
C (L Shaped):
1 1
1 0
D (X Shape):
1 0
0 1