Operation On Row Of Balls

Level pending

*This problem is incorrect as of now. Please don't attempt it until it gets fixed. *

You have some red and blue balls in your pocket. You arrange some of them in a row in such a way that the leftmost ball is blue. Each second, you do the following operation on the row:

  • For all balls except the rightmost one, if the color of that ball in the previous second was equal to the color of the ball to its right, you replace that ball with a red one (if this ball was already red, this has no effect). Otherwise, you replace that ball with a blue one (if this ball was already blue, this has no effect).
  • Add a blue ball to the left of the row.

For example, suppose at some moment the following picture denotes the arrangement of the balls:

image link- http://s21.postimg.org/cfnd4059j/Untitled.png

image link- http://s21.postimg.org/cfnd4059j/Untitled.png

Then, after one operation, the arrangement of the balls will be as follows:

image link- http://s16.postimg.org/yrl14wmo5/Untitled.png

image link- http://s16.postimg.org/yrl14wmo5/Untitled.png

The leftmost ball in the second picture was newly added.

Now, an arrangement of balls is called good if all its balls are blue.

You have an unlimited supply of balls. However, once the length of the row exceeds \(50\), you get tired and stop doing the operations. You want to choose the initial arrangement in such a way that after some operations, the arrangement becomes good.

Find the number of possible initial arrangements of the balls for which, after some (possibly zero) operations, the arrangement becomes good before its length exceeds \(50\). (Once the arrangement becomes good, you stop doing the operations.)

Details and assumptions

  • In particular, if the initial arrangement is already good, it should be added to your count.

  • Consider the initial arrangement \(\{\text{blue, red, blue}\}\). The following picture shows the resulting arrangement after one operation.

    image link- http://s2.postimg.org/yhrwwy9e1/Untitled.png

    image link- http://s2.postimg.org/yhrwwy9e1/Untitled.png

Thus, after one operation, the arrangement is good. This initial arrangement should be included in your count.

  • Note that if the initial length of the arrangement is \(>50\), it doesn't work. So, there are only finitely many possibilities.

  • Once again, remember: the leftmost ball in the initial arrangement must be blue.

  • You are allowed to use a computer program to solve this. However, don't think about trying brute force-- there are \(2^{50}\) possibilities, which is way too large. :)


Problem Loading...

Note Loading...

Set Loading...