Interview Question: Flipping Switches

by Mikael

This came up a long time ago, I only recently recalled it:

Consider a sequence of 100 switches all initially set to “off”. Flip every switch. Now starting with the first switch, flip every second one (i.e. #0, #2, #4, …). Then, starting again with the first, flip every third switch (i.e. #0, #3, #6, …). Proceed in that manner, always starting with the first switch, switching every fourth, then fifth, then sixth switch etc.. Once the first switch has been flipped a hundred times, which switches are set to “on”?

Hint: Consider the X:th switch… On witch of the passes is it flipped?

Solution: It’s a slightly tricky one so I wouldn’t feel bad about not getting it on my own (actually I didn’t and I don’t), but the solution is quite understandable once you see it.

If the X:th switch is flipped by the y:th pass that means y divides X and we can write X=y*z for some z<=X. But then X was also switched by the z:th pass. So the passes that flip X come in pairs and every switch gets flipped an even number of times, but for the curious exception of those for which it can happen that y=z (pretty surprising I thought!). This is only possible if y=z=sqrt(X) so in other words, if X is the square of a natural number, then and only then is it flipped an odd number of times. Those are the switches that will be on after the process is done. The zero:th (#0) switch is of course a special case, but an easy one.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: