3
$\begingroup$

There are 49 lamps set in a circle , and a tool that can toggle the stage(on\off) of any set of 5 consecutive lamps.The lamps are all turned off , and the goal is to switch them on. What are the possible no. of times that one would have to use this tool to achieve this?

The options are $25,32,40 $ and $49$

I have seen many problems of this type , but am clueless as to how to approach them. I feel they may use some algorithmic trick , or algorithmic problem solving strategy, like the invariance principle.

Is there a general way to solve problems of this sort? Also, is there an online source/pdf covering problems like this?

$\endgroup$
1
  • 3
    $\begingroup$ In cases where the toggling is commutative (the set of toggleable lights is independent of which lights are on, etc), these can always be solved using linear algebra over the field $F_2$. Typically the solution space is low-dimensional (the number of toggling patterns is usually equal to the number of lights), so finding the minimum weight vector solution tends to be very inexpensive, though I think it’s NP-hard in general. $\endgroup$
    – Erick Wong
    Jul 12, 2019 at 4:12

2 Answers 2

Reset to default
2
$\begingroup$

The operation (using the tool) is associative and commutative and self inverse, so we can think of solutions as sets of places to apply the tool. (We need not apply the tool in the same place more than once, as these would cancel out.)

Any solution must toggle all the lamps an odd number of times.

In a simplified solution, is it possible for one lamp to be toggled 1 time and an adjacent lamp 3 times? What about 3 and 5?

Is it possible to toggle every lamp exactly 1 time? 3 times? 5 times? How many total times would the tool need to be applied to achieve such solutions?

$\endgroup$
1
$\begingroup$

Since you are looking for $possible$ number of times, and not necessarily the smallest number of times, one solution is $49$ (which is one of your options).

You begin by using the tool on lamps $1-5$, then on lamps $2-6$, ..., then on lamps $46,47,48,49,1$, then on lamps $47,48,49,1,2$,..., and finally on lamps $49,1,2,3,4$.

This way each lamp is switched 5 times and since $5$ is an odd number, the lamps will be on.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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