0

There are $150$ switches. First, You turn on all $150$ switches.Next, you turn off the even indexes.Then you toggles every third index and turn it off if it is on or turn it on if it is off. After $150$th pass. in which you toggle only switch number $150$, how many switches are on?

I solved it "brut force" and I found that the answer is $75$ (correct me if I'm wrong)

But I'm looking for explanation "number theory" style.

Attempt:

$1.$ turn on all $150$ switches

$2.$ turn off all index $i=0\pmod 2$

$3.$ something $\pmod 3$

enter image description here

Error 404
  • 1,892
  • 1
  • 11
  • 23
  • https://www.math.hmc.edu/funfacts/ffiles/10001.4-5.shtml – lab bhattacharjee Mar 11 '17 at 17:37
  • 1
    It seems to me that the switches with an odd number of factors would remain on at the end. Try going through the numbers and note the ones with an odd number of factors. A pattern should arise. – Harnoor Lal Mar 11 '17 at 17:37
  • Your brute force only did it three times. You most also do it a fourth time a fifth time and a sixth time... – fleablood Mar 11 '17 at 18:59

3 Answers3

1

THink of it this way:

Take switch $n$. How many times is $n$ toggled? Well, that depends. Depends on what? On how many factors $n$ has. Okay, let me put it this way, when is switch $n$ toggled? Whenever we are doing a number that is a factor of $n$. Okay, so how many times is $n$ toggled? As many times as $n$ has factors.

Does $n$ end up in the on or off position? Well, that depends. On what? How many factors $n$ have. How so; under what condition will it end up in on and under what conditions will it end up in off? Well, it will be on if it has an odd number of factors and off if it has an even number of factors.

Okay, which numbers have an odd number of factors and which numbers have an even number of factors? I have no idea.

Think about it more and get back to me. But consider:

How many factors does a prime number have? (Two, 1 and itself).

How many factors does a composite number like 24 have? (1,2,3,4,um,6,8,12,24, um 8 right?)

$n$ will always have $1$ and $n$ has factors. If it also has $k$ as a factor, can you name any other factor? (Um, $n/k$ will be a whole number, right? So $k*n/k =n$, so $n/k$ is also a factor, right?)

Is $n/k$ and new factor or one you already listed. (Well, it must be a new one as we have only listed $1,n,k$ and $n/k$ is different.)

What if $n/k = k$? (??????)

So, again, which numbers have an odd number of factors and which have an even number of factors? You can try some examples.

=====

"I solved it "brut force" and I found that the answer is 75 (correct me if I'm wrong)"

You are wrong.

fleablood
  • 124,253
  • Um, my brute force or the OP's? Actually this is my favorite puzzle as it can be solve by pure reason. The ones that are on will have an odd number of factors and those that will be off will have an even number for factors. If $k$ is a factor than $n/k$ is also a factor. Factors come in $(k,n/k)$ pairs. That's even unless $k = n/k$. If $k = n/k$ is a factor then there are odd number of factors. $k = n/k$ is a factor if $k^2=n$. The perfect square on on, the rest are off. Pure reason. – fleablood Mar 11 '17 at 17:57
  • Sorry, I didn't see that 75 was a quote from OP – Ross Millikan Mar 11 '17 at 18:20
0

Hint -

  1. Turn on (mod 6)

Turn off (mod 3).

Hope it helps you.

Amar
  • 847
0

Hint:

Go through $16$ or $17$ switches as a trial run and see what you notice about which switches are still on.

Answer:

Switches in $n^2, \, n\in\mathbb{Z}$ (square numbers) will still be on. The number of squares less than or equal to $n$ is $\lfloor\sqrt{n}\rfloor$. So for $n=150$ the answer is $12$.

Dando18
  • 5,368