# Table with four coins

1,350.2K Views

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.

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.

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