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;
}