Table with four coins

A square table has a coin at each corner.  Design an execution sequence, each of whose steps consists of one of the following operations:

  • ONE:  The operation chooses a coin (possibly a different one with each execution of the operation) and flips it.
  • SIDE:  The operation chooses a side of the table and flips the two coins along that side.
  • DIAG:  The operation chooses a diagonal of the table and flips the two coins along that diagonal.

such that at some point during the execution (not necessarily at the end), a state where all coins are turned the same way (all heads or all tails) obtains.

Share
ronret45 Expert Asked on 1st August 2015 in Microsoft Interview Puzzles.
Add Comment

  • 2 Answer(s)

    There are 3 types of configuration possible:
    (a) all coins have same face up
    (b) 3 coins have same face up (and 1 has the other face up)
    (c) 2 coins have same face up (and other 2 have the other face up)

    Config (a) is the desired final position. Configs (b) and (c) arepotentially one step away from the final position F (where all coins have same side facing up). However, is there a config such that we can choose one of O, S or D and then we are guaranteed to reach the final desired position F ? Yes, there is. A special case of config (c) where the diagonally opposite coins have same face up is such a penultimate position:
    H T     T H
    T H  or  H T
    Applying the D operation here will definitely result in F.

    Perhaps our goal then should be to reach this position F’ from other positions.

    If two coins along a side have same face up, then F can be reached through F’ by the following sequence: S, D.
    Therefore, F can be reached from config (c) by the following sequence:D, S, D.

    If a single coin is face up, then we have the following sequence towards F: O, D, S, D.

    Applying this sequence to config (b) will definitely lead to F. Applying this sequence to config (c) however might result in config (b). Therefore this sequence must be repeated:
    O, D, S, D, O, D, S, D.

    This is the desired sequence of operations which will guarantee that the final position F is reached at some time during its execution.

    ronit Guru Answered on 5th August 2015.
    Add Comment

    DIAG
    SIDE
    DIAG
    ONE
    DIAG
    SIDE
    DIAG
    7 operations in total.

    reducingOdds Starter Answered on 12th July 2017.
    Add Comment
  • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.
  • More puzzles to try-

  • Tags