Which Switch?
27 Answers 
Challenge Your Friends
Tweet this
From Sean Murphy:
There are 1000 switches numbered from 1 to 1000. They are all off. I begin by flicking all the switches. I then flick every second switch (2,4,6…). I then flick every third switch (3,6,9…). I repeat the process 1000 times.
How many switches are off by the time I have finished?
Get Puzzles Delivered:
969? Unless I scripted it wrong. I’m sure theres some formula though.
I guess it’s all except prime numbers
nope, I was very wrong…
i’m getting 969, too, from my script
Every switch gets flicked as many times as its ordinal number. They all start off; switch #1 is flicked precisely once therefore at the end of the flicking, it’s on. #2 is flicked twice, therefore it’s off (assuming standard SPST-type switches, rather than push-button momentary or other types of switch). And this continues – #3 thrown three times, therefore off, and so on. Therefore the number of switches in the off position is just the number of switches with an odd ordinal number, ie. the number of odd numbers between 1 and 1000, ie. 500
I say 970
Pthoey. Hate typos. #3 is on, all odd switches are on, all even switches are off, the answer is numerically the same (500).
Next time, I have my coffee *before* posting…
@Mark: You are wrong, for example #3 is not switched three times, it’s only switched twice: on the 1st and 3rd “pass”!
I have the mathematical demonstration but I’ll not spoil the fun yet.
A switch is flipped once for each of its factors, including 1 and itself. The only switches that can end up in the on position are the ones with an odd number of factors.
For any number n and factor p, there is a complementary factor q = n/p. So the only way to end up with an odd number of factors is to have two that are the same: n/p = p. This means that only switches whose positions are perfect squares will be left on.
The largest integer whose square is less than 1000 is 31 (32^2 = (2^5)^2 = 2^10 = 1024). So there will be 969 switches that are off.
Very nice, Dan.
Dan is getting there, but it feels a little handwavy.
Let’s say a number $n$ has a prime factorization
$$n=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$$
If we want to assemble a factor of $n$, we have to make it up from these prime factors. We have $e_1+1$ choices of how many copies of $p_1$ to use, $e_2+1$ choices of how many copies of $p_2$ to use, and so on. These choices are all independent, and so $n$ has
$$(e_1+1)(e_2+1)\dots(e_k+1)$$
factors. For a switch to be left on, it must have an odd number of factors, and so each of these terms must be odd. Thus each of the $e_i$ must be even, and $n$ must be a perfect square.
First correct answer goes to Steven. Azeroth would have been correct if the question was changed only slightly, so that the switches are flicked at most once (twice actually) and never flicked again. Mark also gave a correct answer, but to a misinterpreted question. My friends and I found the answer via the observation that the off switches must have an odd numbers of factors, and the prime power equations given by John. So the first complete explanation comes from John. My favorite reply is from Dan, who’s (partial) explanation is the most succinct I think. He shows that being a square number is a necessary condition for having an odd number of factors but he did not show that it was a sufficient condition, so he can really only use that explanation to get an lower bound on the number of off switches (I think). Dan has shown that if a number has an odd number of factors it will be a square. If someone can show all squares have an odd number of factors using similar logic then we’re done
Thanks to everyone for responding.
answer is 500. the part where flick every third switch (3,6,9…). and repeat the process 1000 times has no impact on the results as it affects the same number of switches.ie if it turns one on ,it also turns another one off.so ignore that, then the answer will be 500.
its 100% 1000
0
I just went for brute force:
switches = [False for x in range(1,1001)]
step = 1
while(step <= 1000):
i = 0
while i < len(switches):
switches[i] = not switches[i]
i += step
step += 1
are_off = 0
for switch in switches:
if switch is False:
are_off += 1
print are_off
prints: 969
The switch no. 1,4,9,16,25…. all the square of number will be on and other all switch will be off as they will be flicked odd no of times where as other all switch ll be flicked even no of times for example switch no 7 will be flicked by 1 and 7 where as switch no 25 will be flicked by 1,5 & 25 as the square root of 25 that is 5 will flick it only once.
.*` I am really thankful to this topic because it really gives useful information -~”
Only squares have odd number of factors, odd number of factors (switching) will lead to change in state of a bulb. Squares from 1^2 to 31^2 fall within 1000, since 32^2 exceeds 1000. So 31 switches have changed state, thus 1000-31 = 969 switches are ON, rest OFF.
Here is my view
In the begining 10000 switches OFF then
– Flicking all the switches will turn ON 1000 switches
Therefore 0 Switches OFF in this step
– Flicking every second switch will turn OFF half the number switches (2,4,6…) and other half are still ON (1,3,5…)
Therefor 500 switches OFF in this step
– Flicking every third switch (i.e. 3,6,9,12..)will turn OFF half of the odd number switches i.e. 3,9,15.. and turns ON half the ODD number swithces i.e. 6,12,18..
so number of switches turned OFF will be balanced by number of switches turned ON for this step
Hence the total Switches turned OFF are 500
By doing this: class Main {
public static void main(String[] args) {
//there are 1000 switches
boolean[] switches = new boolean[1000];
//all switches are off
for (int i = 0; i < switches.length; i++) {
switches[i] = false;
}
for (int step = 1; step <= 1000; step++) { //repeat step 1000 times
//flick every "step" switch
for (int j = 0; j < switches.length; j+=step) {
switches[j] = !switches[j];
}
}
int count = 0;
for (int k = 0; k < switches.length; k++) {
if (!switches[k]) count++;
}
System.out.println("Switches that are off: " + count);
}
}
I get this output:
Switches that are off: 969
Small correction to my previous answer
In the begining 10000 switches OFF then
– Flicking all the switches will turn ON 1000 switches
Therefore 0 Switches OFF in this step
– Flicking every second switch will turn OFF half the number switches (2,4,6…) and other half are still ON (1,3,5…) i.e Even swithcehs OFF and Odd swithces ON
Therefor 500 switches OFF in this step
– Flicking every third switch (i.e. 3,6,9,12…999) will turn OFF alternative ODD switches (since ODD swithces were OFF earlier) and turns ON alternative Even switches (since Even swithces were ON earlier).
Since start and end (3,999) are ODD numbers therefore the net effect of this iteration would be 1 switch turned OFF
Therfore Total number of swithces Turned OFF are 501
Answer –
999 switches will be off by the time the whole process is done. Only one will remain on. Switch number 1.
//sry i made a mistake in on and off// changes to above answer of mine.
Answer –
999 switches will be off by the time the whole process is done. Only one will remain off. Switch number 1.
lol wtf. i want to write –
999 will be on and 1 will be off. switch number one.
Your artical can be so simple however , retains some elegance together with grace. And together with the options together with customization you’ve got enabled, I’m sure it will eventually appeal to many people bloggers. It’s very commendable that you are interested in let united states, the owners, to have a wide choice of themes for our blogs. Keep them all coming!
man… you sure do have a lot of time on your hands flipping all those switches.