I came across this interesting problem yesterday.
There are few light bulbs and all of them are switched off. On the first turn, you press the switch of all bulbs, i.e. you turn all of them on. On the second turn, you switch all the second bulbs (2, 4, 6…). On the third turn, you switch all third bulbs, and so on.
An example with five bulbs and five steps (where 1 denotes a glowing bulb, and 0 denotes a non-glowing bulb):
00000 (initial)
11111 (step 1)
10101 (step 2)
10001 (step 3)
10011 (step 4)
10010 (step 5)
Hence, in case of five bulbs, the number of glowing bulbs at the end is 2. You have to find out how many bulbs are left glowing after 100 turns when you have 100 bulbs. The solution must be done mentally, without any rigorous calculation.
It is recommended that you try it yourself before reading the solution.
Mental Solution:
Every bulb is off at the beginning. It is apparent that it will remain off if it is switched even number of times. Likewise, it’ll be on if switched odd number of times. Let’s pick a random bulb, say bulb 8. Bulb 8 will be switched on the 1st step, 2nd step, 4th step and the 8th step, i.e. it’ll be switched on a step if the step number is one of its factors.
Merging these two conditions, we have: a bulb will remain on if it has an odd number of factors.
Now we have the task of finding out which digits have odd number of factors. We can always divide a number into a set of two factors. For example, 8 can be divided into (1,8) and (2,4). These factors multiply with each other to give the original number. So we’ll always have even number of factors, unless we get two equal factors, i.e. (x,x). Only perfect squares can be divided into two equal factors.
So the problem boils down to: “How many perfect squares are there under (and including) 100?” The answer is 10. 10 bulbs will remain glowing after the 100th step. (The logic works for any number of bulbs, if the number of steps is equal to the number of bulbs.)
Programmed Solution (using Python):
Such problems can be easily solved through computer programs. It leads to some interesting results.
[sourcecode language=”python” wraplines=”false” collapse=”false”]
print "—THE GLOWING BULB PROBLEM—"
cnt=0
i=0
n=input("Enter number of bulbs: ")
m=input("Enter number of steps: ")
if (m>n):
m=n
a=[0]*n
f1 = open("lights.dat", ‘w’)
f1.write("0"+"\t"+"0"+"\t"+"0"*n+"\n")
for x in range(m):
f1.write(str(x+1)+"\t")
for i in range(x,n,x+1):
if(a[i]==0):
a[i]=1
cnt=cnt+1
else:
a[i]=0
cnt=cnt-1
f1.write(str(cnt)+"\t")
for y in range(n):
f1.write(str(a[y]))
f1.write("\n")
print "\n" * 100
print "Executing… " +str(float((x+1))*(100.0/m))+ "% completed."
f1.close()
print "The file has been created."
print "Number of glowing bulbs = "+ str(cnt)
[/sourcecode]
Result:
—THE GLOWING BULB PROBLEM—
Enter number of bulbs: 100
Enter number of steps: 100
Executing… 100.0% completed.
The file has been created.
Number of glowing bulbs = 10
The data has been written on a file “lights.dat” which when plotted gives:
We can see that 10 bulbs are left glowing after the 100th step. We can also guess at the logic by analyzing the graph. The first region is quite chaotic and we ignore it. Then, there’s a region (before 49) where the number of glowing bulbs remain constant. This is the region where one bulb is turned on and one is turned off in each step. At 49, two bulbs get turned on, resulting in a spike (our first clue, what’s special about 49?). After 50 comes the steady decline, where one bulb is turned off in each step. But as you see, in the each of the steps 64, 81, and 100 one bulb is turned on instead. We can immediately guess that bulbs numbered as perfect squares get turned on at their own step number.
When I opened the data file, I found something remarkable. By the way, the columns here are:
- the step number
- number of glowing bulbs
- the status of bulbs (a 100 digit number containing 0s and 1s denoting the state of each bulb in order)
The pattern of 0s and 1s is obvious. The vertical stripes (green) are obviously the perfect squares. The lower red line is formed because bulbs (except perfect squares) get turned off on their own step number. The upper red line is formed by the halves of the even numbers which turn on the respective numbers’ bulbs.
Note that every number apart from perfect squares get turned off at the lower red line. No change takes place in any bulb below that, and hence, only perfect squares stay glowing.