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:

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

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.

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. :)

The answer is 84.

1 solution

Sreejato Bhattacharya
Mar 21, 2015

Interpret an arrangement as a binary number, where a blue ball denotes a $1$ bit and a red ball denotes a $0$ bit. Then, the operation mentioned is equivalent to multiplying the number by $(11)_2= 3$ . Also, each good arrangement is of the form $2^t-1$ . Thus, the question is equivalent to finding the number of $x$ for which there exists a $b$ such that $3^b \cdot x = 2^t-1$ for some $t \leq 50$ . The following C++ code does this nicely: http://ideone.com/RCb30A

This code prints $\boxed{84}$ , which is our desired answer.

EDIT: Whoops, the operation is not equivalent to multiplying by $3$ . I'l fix this soon.

Operation On Row Of Balls

The answer is 84.

1 solution

0 pending reports