2

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.

Dennis Meng
  • 1,397
user106448
  • 301

2 Answers2

3

The problem may be missing some conditions since the operations allowed are overkill for the conclusion. It should be added that one does not see the coins during the execution of the algorithm.

Any sequence of moves is reversible, so there is a trivial algorithm: cycle through all $16$ possible configurations, for each one making a series of moves that would turn it into a 4-heads state, then reverse those moves and try out the next possibility.

More efficient would be to use a (cyclic) Gray code that goes through all $2^4$ positions once by changing one bit at each step.

Since you allow either 4-heads or 4-tails as winning positions, if there is a cyclic Gray code where positions at step $i$ and $i+8$ are complements (their XOR is $1111$) that would be optimal. Within the first $8$ moves, or $7$ if the starting position is counted as a zero move, moving along the code will hit one of the targets.

zyx
  • 35,436
0

I have seen this puzzle with the restriction that you are blindfolded and the table is spun between each time you get to make a change. You are then allowed to change the state of any coins you choose, but these operations suffice. Under these conditions you can do any table with $2^n$ and the idea is to make sure there are bits both ways at a lower level. So flip every other coin. If they were alternating, you have won. If not, flip every fourth coin. If you don't win, flip every other coin. Now you know there is noise at the $3$ levels down, so flip every eighth coin. Now go back-every other, every fourth, every other. You now know that there is noise four levels down. Keep going.

Ross Millikan
  • 374,822