Problema Solution
A Christmas tree is decorated with 30 lights which are numbered 1-30. Timers are set so that every 5 minutes a change occurs in the light pattern. The sequence of change repeats every 3 hours. Switches are set so that at the end of the first time interval, every light is turned on; at the end of the second interval, every second switch is reversed; at the end of the third time interval , every third switch is reversed and so on. What is the state of the lights at the end of the first 3 hours?
Answer provided by our tutors
The timers must be set to change every 6 min since in 3 hours we must have 30 changes (we have only 30 lights)and 180/30 = 6.
Otherwise if they are set to change every 5 min then it is not defined what will happen at the end of the 31 or 32 or 33 or 34 or 35 or 36 interval (since 180/5 =36).
We will solve the problem by assuming that the change is every 6 minutes.
Let a1,a2,a3,....,a30 are the numbered lights. We will assign value 1 if the light is on and value 0 if the light is off.
End of interval 1: the situation is like this ak = 1, where k =1,..,30
End of interval 2:
a1 = 1 stays the same k<2
ak = 1 stays the same if 2 doesn't divide k and k>=2
ak switch is reversed if 2 divides k and k>=2
Thus we have
a1 = 1, a2=0, a3=1, a4=0,....
........
End of interval t (t<=30):
ak stays the same if k<t
ak switch is reversed if k>=t and t divides k
We can determine the number of switching for ak using the number of different dividers of k counting 1 and k as well. That is
ak = 1 if k =1
ak = 0 if k has even number of dividers
ak = 1 if k has odd number of dividers
or the general solution after 30 intervals is
ak = 1 if k =1
ak = 0 = (-1)^n1 - 1 if k has even number of dividers = n1
ak = 1 = (-1)^(n2+1) if k has odd number of dividers = n2
Thus after the end of interval 30 we will have the following state
a1 = 1
a2 = 0
a3 = 0
a4 = 1
a5 = 0
a6 = 0
a7 = 0
a8 = 0
a9 = 1
a10 = 0
a11 = 0
a12 = 0
a13 = 0
a14 = 0
a15 = 0
a16 = 1
a17 = 0
a18 = 0
a19 = 0
a20 = 0
a21 = 0
a22 = 0
a23 = 0
a24 = 0
a25 = 1
a26 = 0
a27 = 0
a28 = 1
a29 = 0
a30 = 0
In addition to the solution i want to add that we can find the number of divisors of n using the following theorem:
Let d(n) be the number of divisors for the natural number. If we write the number n as a product of prime factors: n = (p^a)(q^b)(r^c)...
then the number of divisors is d(n) = (a+1)(b+1)(c+1)...
We can write for the solution of our problem:
After 30 intervals we have the following state of the lights:
ak = 0 = (-1)^d(k) - 1 if d(k) is even
ak = 1 = (-1)^(d(k)+1) if d(k) is odd