# Infinity Hotel problem

Q. Welcome to the infinity hotel has an infinite number of rooms $1,2,3,4,...$ The manager notices all of the rooms have the lights on. He flips the switch every other one. (Rooms $2, 4, 6, …$) Then he does the same thing with every third room. (Rooms $3, 6, 9, …$) Then he does the same with every fourth room. (Rooms $4, 8, 12, …$) So on, and so forth, the process continues on forever. Of the first million rooms, how many lights get left on.

So I know by testing cases that all the prime number rooms will be left off because the only divisors are 1 and itself so when he gets to the prime, he just shuts it off and never goes to it again. Then I found by cases that every Squared room (i.e. room $1, 4, 9, 16, 25, ..., (1000^2$) remains on). By testing I can see that these are the only rooms that remain on, and there are 1000 of them but I'm not sure how to prove it. I know it has to do with Tau(n) and possibly Sigma(n).

edit: So here is what I came up with, feel free to comment about it:

We establish τ(n) for our question by seeing τ(n) can either be odd or even. By question 2[Let n be a positive integer, prove that n is a perfect square ⇔ τ(n) is odd.], τ(n) is odd ⇔ n is a perfect square, otherwise τ(n) is even. When τ(n) is odd it can be noticed that the room is reached an even number of times since we are disregarding 1 as a divisor. That is, each odd time a room is reached the lights are turned off, and every even time the room is reached the lights are turned on. Moreover, the only rooms that are reached an even number of times are the perfect squares and these are the only rooms that are left on. Then we can see that $1000^2 = 1000000$, and we include this room in our question. We can conclude that rooms $1^2, 2^2, 3^2, … 999^2, 1000^2$ are the only rooms left with the lights on, so there are $1000$ of them.

It really requires a lot of thinking, I hope my logic is correct.

-
Am I missing something? All the lights will be turned off. Even the primes. EG, room 17 will be turned off when he flicks the switches 17,34,... –  Frank Mar 31 '14 at 22:08
@Frank he said flips, not turns off. –  user2345215 Mar 31 '14 at 22:10
@user2345215 Ok, thanks, I was missing something! –  Frank Mar 31 '14 at 22:10
So for example, he turns room 2,4,6,8,... off, then he turns 3 off but 6 back on, then 9 off, but 12 back on... –  User011123521 Mar 31 '14 at 22:12
@Michael I don't think the bill is sufficient. For if every second light was on, the bill would also be infinite. (or every 3rd, 4th.. etc) –  Cruncher Apr 1 '14 at 15:32

Back up a step: assume the hotel starts off dark, and that on the first pass every light is turned on. You can easily see that this is the same problem. A light gets switched each time one reaches one of its divisors. A light ends in the off position iff that number is even, since flicking a switch twice nets no change. Which numbers have an odd number of divisors? The perfect squares.

-
Yeah I've seen this, 1 | 1, odd, 4 | 1,2,4 - (3), odd, 9 | 1,3,9 - (3), odd.. and so forth but not sure how to put this into proof context, but thanks for answers. –  User011123521 Mar 31 '14 at 22:14
If you write this, the only thing left to prove is that you have an odd number of factors iff you are a perfect square, which is quite easy. –  Joshua Biderman Mar 31 '14 at 22:16
Also, you're notation is wrote. 5|10 is true. 10|5 is false. $(a|b)\iff(\exists k)(ak=b)$ –  Joshua Biderman Mar 31 '14 at 22:17
Yes, sorry about that, but conveniently proving an odd number of factors iff you are a perfect square, is the previous question from my work. –  User011123521 Mar 31 '14 at 22:18
The formula for $\tau$ also will tell you perfect square iff odd number of factors. –  Joshua Biderman Mar 31 '14 at 22:20

No need for needlessly complicated solutions.

If $d$ is a divisor of $n$, then $\frac nd$ is also a divisor of $n$. If we pair them, we see that the number of divisors is even, unless there's a divisor $d$ such that $d=\frac nd\Longleftrightarrow d^2=n$, i.e. $n$ is a perfect square. In that case, the number of divisors is odd.

-
Indeed, no need for needlessly anything. –  Andres Caicedo Mar 31 '14 at 22:46

The final state on room $n$ depends on how many divisors $n$ has: if it has an odd number of divisors, then the light will end up begin on; if it has an even number of divisors, the light will end up off.

So, which numbers have an odd number of divisors? If the prime decomposition of $n$ is $$n=p_1^{a_1}\cdots p_k^{a_k},$$ then we obtain all possible divisors of $n$ by forming the numbers $p_1^{r_1}\cdots p_k^{r_k}$, with $0\leq r_j\leq a_j$. So we have $a_j+1$ choices for $r_j$: the total number of divisors is then $$(a_1+1)(a_2+1)\cdots(a_k+1).$$ For this number to be odd, all of $a_1,\ldots,a_k$ need to be even (otherwise, $a_j+1$ would be even for some $j$, making the product even). So $a_j=2b_j$, say, and $$n=(p_1^{b_1}\cdots p_k^{b_k})^2.$$ So the positive integers with an odd number of divisors are precisely the squares.

-