An interview riddle seen by a mathematician
Note to the reader: Python code and visualizations are shared at the end
The riddle
When I was applying for a quant position in an Investment Bank in London a couple of years ago, I was asked some riddles at the end of the interview. One of them goes like this :
“100 light bulbs are displayed in a line, numbered from 1 to 100. Each light bulb is turned on and off just by pressing its switch. They’re all turned off at inception. Then 100 traders arrive. The first trader comes in and presses the switch of each light bulb from 1 to 100. Now they’re all turned on. The second trader comes in and presses the switch of the second light bulb, then the fourth, the sixth and so on until 100 (therefore turning them off, since all were turned on by the previous trader). The third trader comes in and presses the switch of the third (turning it off), sixth (turning it on), nineth and so on. Up until the 100th trader presses the switch of the 100th light bulb.
Question is: how many light bulbs are turned on in the end?”
I had the chance to know this riddle when I had the interview, it was part of the knowledge you had to know before applying in a bank. What’s fun is when you tweak this riddle a little. But let’s go first inside the answer.
The bad way to answer this riddle is by trying to count the number of bulbs that are turned on at each step. This is so complex that you’ll probably mess up things, and you’re short on time already.
The correct way is to take a random bulb and see what happens. Let’s take bulb number 12. Is it turned on or off at the end? Well, the first trader turns it on, then the second trader turns it off (since he switched the 2nd, 4th, …, 10th, 12th, 14th…). Then the third turns it on again (3, 6, 9, 12). If we continue, we see that the 1st, 2nd, 3rd, 4th, 6th, 12th traders pressed its switch. So: on, off, on, off, on, and off. The 12th light is off.
We see that the n-th light bulb is turned off if its number of divisors is even (combination of ON-OFF). Inversely, it is turned on if its number of divisors is odd. So the question of the riddle can be rephrased as follows: between 1 and 100, how many numbers are there with an odd number of divisors? Well, thinking about it will lead you to squared numbers. Squared numbers are the only ones with an odd number of divisors. Between 1 and 100, well there are just as many as 10 squared numbers, since 1 = 1² and 100 = 10², so all squared numbers between 1² to 10² are 1², 2², 3², …, 9² and 10². Check the code at the end of the article for the computational proof.
But staying there would be no fun.
Bringing randomness into the game
Now imagine the traders had a party before showing up, and got themselves a little drunk. When their turn comes to press the switches, there is now the possibility of them forgetting to press a switch and continue. Let’s say all traders now have a fifty-fifty chance to press the switch whenever they should actually press it.
The experiment starts again. The 100 bulbs are turned off. The 100 traders press (or not) the light bulbs with the same rules than before, with the 50–50 chance.
Once again, the question is: how many light bulbs are turned on in the end?
Now the riddle seems way too twisted. But what if I tell you the answer is surprisingly simple. Its simplicity is even mind-boggling.
Let’s look at the problem the same way we did previously. Let’s pick light bulb number 12. In the end, is it on or off? Traders 1, 2, 3, 4, 6 and 12 have a 50–50 chance to press the switch. Performance of trader 1 is independent of performance of trader 2. This also holds true for traders 3, 4, 6 and 12. The light bulb is turned ON if and only if there is an even number of traders that pressed the switch.
The question for light bulb number 12 becomes: what is the probability of an even number of traders pressing its switch, knowing the traders are number 1, 2, 3, 4, 6 and 12?
Let’s pause a second.
Do you see it?
Still not?
Let me help you. It’s quite tricky to explain in short, but in the end it’s fifty-fifty. You have to remember that if you flip n coins, then the chance of getting an even number of heads is the same as getting an odd number of heads, since all coins have a fifty-fifty chance to be heads. So the probability for light bulb 12 to be on is 50–50. Same for every other light bulb. Whatever the number of divisors.
Let’s realize what we discovered. If there’s no randomness, then we’ll get 10 light bulb that are turned on in the end. If there’s a 50–50 chance to press the switch, then we’ll get 50 light bulbs that are turned on.
How come? We went from 10 to 50, just by introducing some “noise” in the process. 50 is a lot more than 10. 50 out of 100 is actually quite regular, whereas 10 out of 100 is quite unexpected. By adding noise, we surprisingly arrived at a more intuitive, general result.
Well, if you do the experience, you’ll have a poor chance to finish with exactly 50 turned on light bulbs. This is because probabilities do not reflect in real life experiences. You’ll have to repeat the experiences thousands and thousands of times, and average the results, and then you’ll get close to 50 (cf Law of large numbers.) The code added at the end of article helps visualize that.
What if the probability is different from 1/2?
Going from 10 to 50 turned on bulbs was quite interesting. By changing the probabilities, can we go to more than 50 turned on bulbs? What is the rate at which the number of turned on bulbs increases? Answers below.
Mathematics are amazing in various ways, but one way that is particularly relevant in our case, is continuity. Having the probability vary from 1 to 0.5, the (expected) number of turned on light bulbs will go continuously from 10 to 50. We can also surmise what will happen if the probability is 0, then no switch gets pressed, and no light is turned on. Therefore going from 10, to 50, to 0 by decreasing p from 1, to 0.5, to 0. Close to symmetry, but not actually symmetric.
The shape of the curve tells us a lot of information:
- From p = 0 to p = 0.5 the number of turned on bulbs increases from 0 to 50
- p = 0.5 is actually the peak of the curve: there’s no other p that makes it more likely to get more than 50 turned on light bulbs
- From p = 0.5 to p = 1 the number of turned on light bulbs keeps going down until it reaches its minimum at p = 1, where only 10 bulbs are turned on
Make sure to check the code for this article, it uses Jupyter Notebook: https://github.com/FelixChop/MediumArticles/blob/master/An%20interview%20riddle%20seen%20by%20a%20mathematician.ipynb
