A tedious puzzle (but not homework)

Question

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?

Not homework but a UK university interview question. Please help.

Answer 1

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$.

Answer 2

Each number that is a square will be ON.

Answer 3

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$)

Answer 4

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.

Answer 5

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.

Answer 6

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).