It's twelve o'clock!

Question

The twelve numbers on a clock are each either colored red or colored black. You are allowed to make several moves, where a move consists in picking a black number, and in flipping the colors of its two neighboring numbers (while keeping the color of the picked black number unchanged). The goal is to reach a situation where eleven numbers are red and where the remaining twelfth number is black.

Question: How many starting situations are there that allow you to eventually reach the goal?

Answer 1

2048

Proof

Each move changes the number of black numbers remaining by 0 or 2, and thus cannot change the parity. Thus initial states with an even number of black numbers can never be brought to the desired state. Now we claim that every initial state with an odd number of black numbers can be brought to the required state. By repeatedly using the moves RBR -> BBB and BBR ->RBB, it is possible to move to a state where all the black numbers are together (To see this, note that B_RBB can be turned into B_BBR, and B_RBR to B_BBB). The following steps can be used to reduce the chunks:

• B
• BBB -> RBR = B
• BBBBB -> RBRBB -> RBBBR = BBB
• BBBBBBB -> RBRBBBB -> RBBBRBB -> RBBBBBR = BBBBB and so on

Thus all 2048 stateswith odd number of black numbers can be reached

This code which counts the number of reachable states confirms the result:

char seen[1<<12];

int dfs(int state)
{
  seen[state]=1;
  int ret=1;
  for(int i=0;i<12;i++)
  {
    if((state&(1<<i))==0)continue;
    int l=(i+1)%12,r=(i+11)%12;
    int nextstate=state^(1<<l)^(1<<r);
    if(!seen[nextstate])
      ret+=dfs(nextstate);
  }
  return ret;
}

int main()
{
  int cnt=0;
  for(int i=0;i<12;i++)
  {
    if(!seen[1<<i])cnt+=dfs(1<<i);
  }

  printf("%d\n",cnt);
  return 0;
}