Quarter flipping on a spinning table

This week’s Riddler Classic is a simple-sounding problem about statistics. But it’s not so simple! Here is a paraphrased version of the problem:

There is a square table with a quarter on each corner. The table is behind a curtain and thus out of your view. Your goal is to get all of the quarters to be heads up — if at any time all of the quarters are heads up, you will immediately be told and win.

The only way you can affect the quarters is to tell the person behind the curtain to flip over as many quarters as you would like and in the corners you specify. (For example, “Flip over the top left quarter and bottom right quarter,” or, “Flip over all of the quarters.”) Flipping over a quarter will always change it from heads to tails or tails to heads. However, after each command, the table is spun randomly to a new orientation (that you don’t know), and you must give another instruction before it is spun again.

Can you find a series of steps that guarantees you will have all of the quarters heads up in a finite number of moves?

Here is my solution:
[Show Solution]

7 thoughts on “Quarter flipping on a spinning table”

  1. Cool. I suppose it depends a bit on what is meant by
    “Can you find a series of steps that guarantees you will have all of the quarters heads up in a finite number of moves?”

    If asserting that the number of moves is finite With Probability 1 is enough, I think a simple decision rule of at each position saying ‘flip kth coin’ and ‘do nothing’ (being n+1 distinct mutually exclusive choices selecting one at random, each with equal probability of $\frac{1}{n+1}$) is enough to guarantee an aperiodic, irreducible finite state (time homogenous) markov chain that includes all possible configurations. All states are visited WP1 and the time until first visit is stochastically smaller than some geometric random variable.

    This is the random walk approach.

    1. Agreed.

      My take was different: I interpreted the question to mean that the algorithm had to have a uniform bound on stopping time that was robust to adversarial table spins. So really, I assumed the table spins weren’t random at all.

    1. I did some statistical analysis over several hundred trials and found that the distribution of the number of steps required to reach a solution is pretty flat. I thought there might be an expectancy of some likely number of steps (a bell curve) but that wasn’t the case.

    2. 15 moves maximum.

      A4 = flip all 4 coins
      BR= flip bottom right coin
      TLBR= flip top left, bottom right coins
      B2= flip bottom 2 coins

      I think the following sequence of steps will win every time:

      A4
      BR
      A4
      TLBR
      A4
      B2
      A4
      TLBR
      A4
      BR
      A4
      B2
      A4
      TLBR
      A4

  2. Nice illustration of the state diagram!
    To be pedantic, it’s probably more accurate to say this problem is about probability (or combinatorics) than statistics 😉

Leave a Reply

Your email address will not be published. Required fields are marked *