IIT JEE , AIEEE Forum - Mathematics , Algebra

elastiboysai

Heres anoder interesting question

There are (n > 1) lamps L₀, L₁, ... , L_n-1 in a circle. We use L_n+k to mean L_k. A lamp is at all times either on or off. Initially they are all on. Perform steps s₀, s₁, ... as follows: at step s_i, if L_i-1 is lit, then switch L_i from on to off or vice versa, otherwise do nothing. Show that:

(a) There is a positive integer M(n) such that after M(n) steps all the lamps are on again;

(b) If n = 2^k, then we can take M(n) = n² - 1.

(c) If n = 2^k + 1, then we can take M(n) = n² - n + 1.

konichiwa2x

This is again another famous olympiad problem. (IMO - 1993)

Solution to (A)

First, the sequence cannot terminate: it can only terminate if it reaches configuration with all lamps off, which is not possible, since if after some step $S_{k}$ the configuration is all lamps off, that must have been the configuration before step $S_{k}$ , so backtracking, the initial configuration must have been all off, which isn't true. Consider the infinite set of configurations after $nt$ steps for some integer $t$ . Since there are only finitely many different configurations, some two must coincide. Choose the first such pair, after say $i$ and $j$ steps. So after $j$ steps, the configurations just cycle. Now consider backtracking from step $i$ to step $1$ (by backtracking, replace the relavent pair of switches as follows:

(0,0) and (0,1) are unchanged, (1,0) goes to (1,1) and (1,1) goes to (1,0) ) :

consider the sequence of steps taking step $i$ to step $1$ . Now applying the same sequence of steps to step $j$ , we can see by backtracking, after exactly $i$ steps we will reach a configuration with all lamps on.

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.

konichiwa2x

Solution to (C)

Let's keep the notation from proof of (b) (i.e., the $K_{i}$ notation), and let $K'_{i}$ denote the arrangement obtained after $ni$ turns (but here $n = 2^{k} + 1$ , and not $n=2^{k}$ ).

By looking at case $k=2$ and comparing $K_{i}$ with $K'_{i}$ , the following pattern becomes obvious: for $i=1, 2, ... 2^{k}$ , configuration $K'_{i}$ is obtained from $K_{i}$ , by shifting $K_{i}$ in cyclic direction twice, and adding in a $0$ for the lamp in position # $1$ . We can prove this by using induction, and our equation $(1)$ which tells us how to get configuration $K'_{i+1}$ from $K'_{i}$ . Using this, we can see that $K'_{n-2}$ , every lamp except for lamp # $2$ is a $0$ . Using equation $(1)$ , $K'_{n-1}$ consists of all lamps except lamp # $1$ being a $1$ . Thus, after one more step, all the lamps become $1$ -s - so in $n(n-1)+1 = n^2 -n +1$ steps, all lamps are on again.

Hence proved.

konichiwa2x

Here is the official solution. (IMO 1993)

http://www.at.itu.edu.tr/gungor/IMO/www.kalva.demon.co.uk/imo/isoln/isoln936.html

(PS. Please dont rate me for the above solutions. They are not entirely mine).

Radon222

Sorry dude ! I can't restrain myself from rating you.

vineetnegi

I dont know how to do it mathematically but the word retracing caught my eyes

i retraced the sequence

and obtained the following figure

let all lamps are lit

steps(each cycle) no. of lamps

(1 on)(0 of)

1111(initially all lamps are lit)

(steps are retraced ) 1000

1100

1010

1111

after every one in previous step of previous column change the state

11

0

as you can see

that for 4 lamps

after 4 steps back lamps are relit

proceed same way you get for power of 2

I dont know how to write it mathematically

but can these tupe of question come in IIT

Ask & Discuss Questions with Community & Experts