Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Jun 16, 2014

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?

The same problem is there on the blog - in a different form - asked more than 50 months back :-) - Blind Flipping - CSE Blog


3 comments:

  1. Following strategy assures all heads or all tails on all corners of the square in 8 turns:

    Nomenclature 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.

    ReplyDelete
    Replies
    1. Solution here: http://www.cseblog.com/2009/11/blind-flipping.html

      Delete
  2. Clarification on arrangements:
    Each 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

    ReplyDelete