The 100 Light bulbs problem

Question

You have 100 light bulbs each one connected to an ON/OFF switch.

Switch 1 corresponds to light bulb 1, switch 2 to light bulb 2……………..switch 100 to light bulb .

All of them are currently off.

On Pass 1 you press every single switch. (Therefore all of the light bulbs are now turned on)

On Pass 2 you press every 2nd switch  (2,4,6………….98,100). Therefore every 2nd light bulb will be turned off.

On Pass 3 you press every 3rd switch ( 3,6,9……….96,99)

On Pass 4 you press every 4th switch ( 4,8,12……….96,100)

You continue this process so in the last two passes will involve pressing every 99th switch followed by pressing every 100th switch.

How many and which of the light bulbs will remain turned on ?

Answer:

Ten lightbulbs  ( 1,4,9,16,25,36,49,64,81,100)

What is common about these 10 numbers is that they are all perfect squares.

Hence the number of times their switches will be pressed will be an odd number and therefore they will end up being switched on since all light bulbs are initially turned on.  This is because numbers which are perfect squares have an odd number of factors unlike the rest of the numbers that have an even number.

You can see bellow all numbers from 1 to 100 with their factors.  Observe how the perfect squares have an odd number of factors unlike rest of them that have an even.

Number Factors
1 1 
2 1,2
3 1,3
4 1,2,4 
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
9 1,3,9 
10 1,2,5,10
11 1,11
12 1,2,3,4,6,12
13 1,13
14 1,2,7,14
15 1,3,5,15
16 1,2,4,8,16 
17 1,17
18 1,2,3,6,9,18
19 1,19
20 1,2,4,5,10,20
21 1,3,7,21
22 1,2,11,22
23 1,23
24 1,2,3,4,6,8,12,24
25 1,5,25 
26 1,2,13,26
27 1,3,9,27
28 1,2,4,7,14,28
29 1,29
30 1,2,3,5,6,10,15,30
31 1,31
32 1,2,4,8,16,32
33 1,3,11,33
34 1,2,17,34
35 1,5,7,35
36 1,2,3,4,6,9,12,18,36 
37 1,37
38 1,2,19,38
39 1,3,13,39
40 1,2,4,5,8,10,20,40
41 1,41
42 1,2,3,6,7,14,21,42
43 1,43
44 1,2,4,11,22,44
45 1,3,5,9,15,45
46 1,2,23,46
47 1,47
48 1,2,3,4,6,8,12,16,24,48
49 1,7,49 
50 1,2,5,10,25,50
51 1,3,17,51
52 1,2,4,13,26,52
53 1,53
54 1,2,3,6,9,18,27,54
55 1,5,11,55
56 1,2,4,7,8,14,28,56
57 1,3,19,57
58 1,2,29,58
59 1,59
60 1,2,3,4,5,6,10,12,15,20,30,60
61 1,61
62 1,2,31,62
63 1,3,7,9,21,63
64 1,2,4,8,16,32,64 
65 1,5,13,65
66 1,2,3,6,11,22,33,66
67 1,67
68 1,2,4,17,34,68
69 1,3,23,69
70 1,2,5,7,10,14,35,70
71 1,71
72 1,2,3,4,6,8,9,12,18,24,36,72
73 1,73
74 1,2,37,74
75 1,3,5,15,25,75
76 1,2,4,19,38,76
77 1,7,11,77
78 1,2,3,6,13,26,39,78
79 1,79
80 1,2,4,5,8,10,16,20,40,80
81 1,3,9,27,81 
82 1,2,41,82
83 1,83
84 1,2,3,4,6,7,12,14,21,28,42,84
85 1,5,17,85
86 1,2,43,86
87 1,3,29,87
88 1,2,4,8,11,22,44,88
89 1,89
90 1,2,3,5,6,9,10,15,18,30,45,90
91 1,7,13,91
92 1,2,4,23,46,92
93 1,3,31,93
94 1,2,47,94
95 1,5,19,95
96 1,2,3,4,6,8,12,16,24,32,48,96
97 1,97
98 1,2,7,14,49,98
99 1,3,9,11,33,99
100 1,2,4,5,10,20,25,50,100