2
$\begingroup$

Lets assume you have a room of 10 switches that are all turned off. You also have 10 robots named 1-10. Starting with robot #1, it goes over and flips all of the switches divisible by its name. When I said flip, I mean it flips the switch in the opposite direction it is currently in (on or off). So, robot #1 would flip all switches on.

Then, robot #2 comes over and flips all of the switches divisible by its name. So robot #2 would flip every even switch.

Then robot #3 comes over and flips all of the switches divisible by its name. So robot #3 would flip every 3rd switch in the series.

This continues on until the last robot, #10, has finished it's turn. By the end of this process, how can we determine how many switches will be "ON"? Is there generalized process to figure out this sort of problem? I don't necessarily want the answer, I just am curious how you would go about figuring this out.

$\endgroup$
1
  • 2
    $\begingroup$ This is usually called the Locker Problem, and instead of switches being flipped it's school lockers being opened and closed. $\endgroup$ – Karl Apr 21 at 6:55
3
$\begingroup$

Let $d(n)$ be the number of divisors of $n.$ Switch $n$ will be flipped $d(n)$ times and its end state will be $(-1)^{d(n)}$ where $-1$ means "on" and $+1$ means "off".

Note that $d(n)$ is even if and only if $n$ is a perfect square.

This is enough to answer your question.

$\endgroup$
2
  • 3
    $\begingroup$ I think you mean "$d(n)$ is odd if and only if $n$ is a square number". $\endgroup$ – Karl Apr 21 at 6:54
  • 1
    $\begingroup$ The divisors of $n$ can be put into pairs $\{k,n/k\}$, with at most one divisor ($\sqrt n$, when $n$ is square) left unpaired. $\endgroup$ – Karl Apr 21 at 7:01
3
$\begingroup$

Rather than thinking from the perspective of each robot going over to the switches, think from the perspective of the switches.

Say if you are Switch 8, which robots are going to flip you? (It’s 1,2,4 and 8.) Why did these robots flip you and not others?

So now, if you are some switch n, you should be able to tell me which robots will flip you - but more importantly, you should consider the number of robots that flip you. If it’s an even number of robots, your end state is off, If it’s odd, your end state will be on.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.