6
$\begingroup$

A play of Romeo and Juliet is being held in the theatre tonight, hundred of people have been waiting this moment for months.
Many people are currently working hard in the theatre to adjust the final details.
Ernest's job is to ensure an adequate lighting in the theatre, else it would be impossible for the actors to perform.
Today, Ernest is experiencing a weird issue with his $1000$ lights: when he triggers the switch of the $i_{th}$ light, it changes status along with all its multiples. For example, triggering the $3$rd switch will change status to the lights with index $3,6,9,12,...$.
Suppose that all the lights are initially off.
Ernest is not a mathematician and is in hurry, so you must tell him how many lights will be on if he triggers all the switches.
You tell him the answer and he thinks that this number of lights is enough. Unintentionally, when it's the right moment to turn on the lights, he breaks the first five switches because of haste!
Now he wants to know the maximum number of lights he can turn on! Is it still enough for the play?

Notes: The broken switches are off.

Improve this question
$\endgroup$
15
  • $\begingroup$ Just to clarify, when he breaks the switches no lights have been affected yet? Also, how many lights are required to be on to be 'enough for the play'? $\endgroup$
    – Mark N
    Apr 27, 2015 at 20:07
  • $\begingroup$ Yes! The first answer is an adequate number, confront the second answer with it $\endgroup$
    – leoll2
    Apr 27, 2015 at 20:11
  • $\begingroup$ Are we to assuming in the first part he flips the switches only once and consecutively from 1 to 1000? Also is he only allowed to flip each switch once in the second scenario (in any particular order)? $\endgroup$
    – Mark N
    Apr 27, 2015 at 20:18
  • $\begingroup$ @MarkN order is unimportant; these are toggles. If you flip switches $S_3$ and $S_6$, light $L_3$ is on and $L_6$ is off, regardless of order. $\endgroup$
    – Ian MacDonald
    Apr 27, 2015 at 20:21
  • 1
    $\begingroup$ @VincentAdvocaat The switches are in a room where you can't see the lights directly. Anyway, perhaps we should stop messing with the story and focusing on the problem :) $\endgroup$
    – leoll2
    Apr 28, 2015 at 13:01

1 Answer 1

Reset to default
12
$\begingroup$

The only numbers which would end up on if he triggered all the switches are:

Squares, since they are the only numbers with an odd count of divisors. There are 31 squares (the squares of 1-31, obviously) between 1 and 1000, and therefore there would be 31 lights on if he triggered all the switches.

Once he breaks switches 1-5, however:

The math gets a bit weirder here with numbers that are divisible by 2-5, but one thing we can be sure of is that prime numbered lights will now be turned on, since their only other divisor is 1, which is now broken. There are 165 primes between 6 and 1000. Since 31 lights were sufficient, 165 lights will certainly be sufficient as well.

EDIT: For conclusiveness, the answer to part 2 is 540 lights. These lights are the numbers where the count of that number's divisors in [1,2,3,4,5] (plus one if the number is a square) is odd. This means that the switch would be hit an odd number of times fewer than the first scenario, which would result in it being on instead of off. The exception is squares, which would need to be hit an even number of times to stay on, which is why 1 is added to the previous sum.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The first answer is correct! The second answer is actually a valid observation, but doesn't say the maximum. +1 $\endgroup$
    – leoll2
    Apr 28, 2015 at 12:13
  • $\begingroup$ I've edited my answer to fully answer your question! $\endgroup$
    – Bailey M
    May 19, 2015 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.