IIT JEE , AIEEE Forum - Mathematics , Algebra

konichiwa2x

Solution to (B)

Let's looking at the configurations $K_{i}$ , where $K_{i}$ is the configuration obtained after $ni$ steps. Denote $K_{i,j}$ be the number assigned to light $j$ in configuration $K_{i}$ .It's easy to see that, working in $(mod$ $2)$ , $K_{i+1, 1} = K_{i,0} + K_{i, 1}$ . (This is true, since two adjacent numbers (1,1), (1,0), (0,0), (0,1) are changed to (1,0), (1,1), (0,0), (0,1) respectively). From there, an induction gives us, that for $1 leq j leq n$ , $K_{i+1, j} = sum_{l=0}^{j} K_{i,l} ... (1)$ .
Looking at Pascal's triangle, for $i=1,2$ we notice that the sequence:

$K_{i,0}, K_{i,1} ... K_{i,n-1}$ is identical to $inom {i} {i} , inom {i+1} {i}, ... inom {i+n-1} {i}$ .

Using $(1)$ , and well-known properties of Pascal triangle (i.e.:

$inom {n+1}{k+1} = inom {n}{k} + inom {n}{k+1}$ ), and induction, we can see that this pattern

is true $i=1,2 ... n-1$ . In particular, let's look at configuration $K_{n-1}$ : for

$1 leq i leq n-1$ , we have $K_{n-1, i} = inom {i+n-1}{i} = inom {2^{k} - 1 + i}{2^{k} - 1}$ .

But since the binary representation of $2^{k} - 1 + i$ contains at least one $0$ , and $2^{k} - 1$ contains only $1$ -s, it follows that, working in $(mod$ $2)$ , $K_{n-1, i} = 0$ for $i=1,2 ... n-1$ - so after $n(n-1)$ steps we end up with a configuration with a $1$ for light # $0$ , and a $0$ for every other light.

From there, after $n-1$ steps, since each following steps toggles one light, we will have configuration with all lights on.

Ask & Discuss Questions with Community & Experts