Problem: 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 (O): The operation chooses a coin (possibly a different one with each execution of the operation) and flips it.
* SIDE (S): The operation chooses a side of the table and flips the two coins along that side.
* DIAG (D): 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.
Solution:
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) are potentially 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.
Subscribe to:
Post Comments (Atom)
1 comment:
Don't know if you'll see this, but doesn't D S D O D S D work as well?
First D resolves the special case of c). The first D has no impact on the other case of c), so the second and third operations resolve the second case of c). The last four terms resolve the case involving b).
Post a Comment