IIT JEE , AIEEE Forum - Mathematics , Algebra

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.

Ask & Discuss Questions with Community & Experts