# The final state of 1000 light bulbs switched on/off by 1000 people passing by

There are 1000 light bulbs and 1000 tutors. All light bulbs are off. Tutor 1 goes flipping light bulb 1,2,3,4... tutor 2 then flips 2,4,6,8... tutor 3 then 3,6,9...etc until all 1000 tutors have done this. What is the status of light bulb 25? 93? 576? Is there a general solution to find out the status of any light bulb? How many light bulbs are on after all 1000 tutors have gone by?

-
How might you go about figuring out how many times a particular switch gets flipped? – Qiaochu Yuan Nov 21 '10 at 15:03
Stan Wagon wrote up (in the solution to one of the POWs) a very general solution to the inverse of this sort of problem-if you know what set of lockers you want locked, what instruction do you give to the tutors to produce it? Unfortunately, I don't have it. – Ross Millikan Nov 21 '10 at 15:11
Hint: if a number $n$ is divisible by $k$, it is divisible by $n/k$. – trutheality Nov 21 '10 at 16:10

Hint: Bulb number $N$ will be flipped by all tutors with number $m$ such that $m$ divides $N$ and no others.

For e.g. light bulb number $36$ will be flipped by tutors numbered $1,2,3,4,6,9,12,18,36$, so $9$ times. Since every bulb was initially off, an odd number of switches will turn it on, which is what will happen with number $36$.

-

The first tutor will flip switches: $$\begin{pmatrix}1&1&1&1&1&1&1&1&\ldots\end{pmatrix}$$

The second tutor will flip switches: $$\begin{pmatrix}0&1&0&1&0&1&0&1&\ldots\end{pmatrix}$$

The third, fourth, ..., eighth will flip switches: $$\begin{pmatrix} 0&0&1&0&0&1&0&0&\ldots\\ 0&0&0&1&0&0&0&1&\ldots\\ 0&0&0&0&1&0&0&0&\ldots\\ 0&0&0&0&0&1&0&0&\ldots\\ 0&0&0&0&0&0&1&0&\ldots\\ 0&0&0&0&0&0&0&1&\ldots\\ \end{pmatrix}$$

The column sum of which is the $\sigma_0(n)$ function (number of divisors): $$\begin{pmatrix} 1&2&2&3&2&4&2&4&\ldots\\ \end{pmatrix}$$

So, when $\sigma_0(n)$ is odd, the light is on, when even, off; but $\sigma_0(n)$ is only odd when $n$ is a square number (because only then you can not pair every divisor).

The total number of on-lights from initial $n$ bulbs, is $$\sum_{k=0}^{k=n}(\sigma_0(k)\mod 2) = \lfloor\sqrt{n}\rfloor$$

### So

• Light 25 is on (square: $\sigma_0(25) = 3$)
• Light 93 is off (non-square: $\sigma_0(93) = 4$)
• Light 576 is on (square: $\sigma_0(576) = 21$)
• There are 31 lights that are on ($\lfloor\sqrt{1000}\rfloor = 31$)
-

You need to factorise each lightbulb's number. If it has an odd number of divisors then it is ON. If it has an even number of divisors it is OFF. I'm sorry I don't have a general n-th rule though.

To answer the question, 25 is ON, 93 is OFF and 576 is ON.

-
Raskolnikov has put this much more succinctly than me. – Patrick Beardmore Nov 21 '10 at 17:29

Each number that is a square will be ON.

-

Let $n=p_1^{k_1}p_2^{k_2}\cdots p_i^{k_i}$ denote the decomposition of $n$ as a product of powers of distinct primes. The number of divisors of $n$ is the product of the $k_j+1$, it is odd if and only if each $k_j$ is even, hence lightbulb $n$ is on if and only if every exponent $k_j$ is even. Thus $k_j=2\ell_j$ for every $j$, where $\ell_j$ is an integer, and $\sqrt{n}=p_1^{\ell_1}p_2^{\ell_2}\cdots p_i^{\ell_i}$ is an integer.

-

You simply need to look at the number of factors that a given number has. This equals the number of tutors that have "changed" that light bulb. For instance, 7 only has one and itself as a factor, so only 2 tutors affect bulb 7; tutors 1 and 7 (the bulb goes from off, to on then off where it remains). 169 on the other hand, has three factors; 1,13, and 169, so this bulb is affected by the tutors numbered 1,13 and 169 (from off to on to off back to on).

-