Post:
You have three switches in one room and a single light bulb in another room. You are allowed to visit the room with the light bulb only once. How do you figure out which switch controls the bulb? Write your answer in the comments before looking at other answers.
Comment:
If this were an interview question, the correct response would be "Do you have any relevant questions for me? Because have a long list of things that more deserving of my precious time than to think about this!
Impossible even if you know if the light is on or off to start with. Even then, there are 2 possible outcomes which means the solution space halves on each test. 3 divided by 2 is greater than 1 (1.5) so we cannot figure it out in a single test.
That's my recollection of how to solve these from computer science. The classic one is 8 coins and figuring out which one weighs a different amount (and you don't know if it is more or less). You have a scale that tells you which side is heavier (or equal) but it doesn't give readouts (as in it doesn't say a side is X pounds/grams). With only three uses of the scale, how can you find the fake coin? I'm not going to go into the process in depth but because you have THREE outcomes (left heavier, equal, and right heavier) you reduce the solution space (which of the 8 coins is the bad one) by a THIRD each test. The number 8 sort of lures into thinking powers of 2. You can actually do it with 9 coins in 3 tests.
Some of the details of my explanation may be wrong, it's been over a decade since I took that class in college lol. It was my worst professor (while different story lol) but I distinctly remember him talking about this. He had a very thick accent, some form of eastern European or Russian, I'm not really sure what exactly. But he gave us that problem as homework or something or maybe just to think about. And he'd ask us to explain how we'd do it. Whenever someone began to describe something doing like test 4, 2, etc instead of the correct way (which involves using coins you already tested) he'd say "YOU'RE DOOMED!" Then someone else would try, and when they got to a way that wouldn't work "YOU'RE DOOMED!" It was hilarious. Very memorable.
Also the number of outcomes isn't connected to the solution space reduction the way you say. If you don't know whether the fake coin is heavier or lighter, both tilt-right and tilt-left are effectively the same result. So at least your first test really only has 2 meaningful outcomes.
In general, you'll only reduce your solution space DOWN TO (not by) 1/(number of distinguishable outcomes) if the possible solutions are evenly divided among those outcomes. It's easy to have a problem where "result 1 narrows it down a lot, result 2 doesn't tell us much"
Like I said, it's been over a decade, some of the specifics may be lost to me.