5
$\begingroup$

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.

  • 0
    How might you go about figuring out how many times a particular switch gets flipped?2010-11-21
  • 0
    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.2010-11-21
  • 1
    Hint: if a number $n$ is divisible by $k$, it is divisible by $n/k$.2010-11-21
  • 0
    I think, it is given by the euler's totient function $\phi(n)$, depending on whether it is odd or even.2017-02-15

7 Answers 7

11

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

4

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

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.

  • 0
    Raskolnikov has put this much more succinctly than me.2010-11-21
2

Each number that is a square will be ON.

1

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

1

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.

1

First think who will operate each bulb, obviously person #2 will do all the even numbers, and say person #10 will operate all the bulbs that end in a zero. So who would operate for example bulb 48: Persons numbered: 1 & 48, 2 & 24, 3 & 16, 4 & 12, 6 & 8 ........ That is all the factors (numbers by which 48 is divisible) will be in pairs. This means that for every person who switches a bulb on there will be someone to switch it off. This will result in the bulb being back at it's original state.

So why aren't all the bulbs off? Think of bulb 36:- The factors are: 1 & 36, 2 & 13, 6 & 6 Well in this case whilst all the factors are in pairs the number 6 is paired with it's self. Clearly the sixth person will only flick the bulb once and so the pairs don't cancel. This is true of all the square numbers.

There are 10 square numbers between 1 and 100 (1, 4, 9, 16, 25, 36, 49, 64, 81 & 100) hence 10 bulbs remain on.

this is the site i got answer from: http://onepuzzleaday.blogspot.in/2007/11/100-bulbs.html