Lightbulbs
As shown above, I have a row of 8 light bulbs, initially all switched off. There is a button below each light bulb that will toggle the bulb on or off.
I want them to be in an alternating off-on state, as shown below.
To do so, I press a block of consecutive buttons in a row. Here is an example of how it can be done in 4 steps:
Can I do it in less than 4 steps?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
6 solutions
Moderator note:
Just to clarify some confusion in the comments: a "move" consists of picking a consecutive set of switches (like 1-2-3, 4-5-6-7, or 2-3-4-5-6) and then flipping all of them. You can flip all 8 in one move, if you like. However, they need to be consecutive switches, so 2-4-6-8, for example, is prohibited.
If he's abble to press 5 buttons as 1 step, shall he just press 4 buttons to get off-on state? -2-4-6-8
Log in to reply
I'm along this same thought. How can he push 5 at once? Are we missing a key rule in this or something?
Log in to reply
He can press as many buttons as he likes in a move, they just have to all be consecutive in a row (as shown in the example steps).
Dinar's idea doesn't work because 2, 4, 6, and 8 are not consecutive.
Yes. But that would be 4 moves.
It says "I press consecutive buttons in a row".
So he can push buttons 2, 3, 4, 5, 6 in one move.
But he cannot push buttons 2, 4, 6, 8 in one move.
Log in to reply
But he can push just one, e.g. 8 in step №2, is this still a "consecutive buttons in a row"? Can we present this rule in math language? Thank You.
Log in to reply
@Dinar Khabibullin – Sure. In every move, he pushes buttons { n ∣ a ≤ n ≤ b } , where 1 ≤ a ≤ b ≤ 8 .
The description of the problem is not clear, doesn't state the order of the lights cannot be changed (I thought the block of 5 lights could be intermixed). Also it mentions an example, so it's not clear if the logic that shows how the lights are switched on/off can be changed or not
Log in to reply
You need to press "consecutive buttons" and the buttons will toggle each bulb on-off. I confess I'm not sure how you'd rephrase that.
Are you missing the word "consecutive", perhaps?
Log in to reply
My understanding of the example is that buttons pressed are not consecutive: 2,8,3,4 and there is no explanation of the logic that connects the switches to the lights so this seems arbirary
Probably what the problem should say is not that you press consecutive buttons, but that you can chose the connections of the switches to the lights, as long as the lights controlled by each switch are part of a consecutive block (with an example)
Hi, I don't understand how you calculate / count the transition number. Could you please rephrase or explain in a different way or in more detail?
Log in to reply
Consider the situation (O = off, I = on) O O I I O O I I . Draw vertical lines whenever there is a transition from O to I or vice versa: O O ∣ I I ∣ O O ∣ I I ∣ . We also draw a vertical line in front of an initial I or after a final I .
Count the number of vertical lines. This is the transition number. (Here: four.)
Convince yourself that every move either adds or removes a vertical line at the beginning of the section that is pushed; and either adds or removes a vertical line at the end of it. Thus the change in the number of vertical lines in each move is + 2 , 0 , or − 2 .
Log in to reply
[Convince yourself that....... is +2,0, or -2] Please explain more specifically. Thank you.
Thank you for this follow up explanation, it's really more clear :)
Thakn you!!
"Count how many lights are opposite of the light immediately to the left; add one if the first light is on, and one if the last light is on. Call this the transition number."
I would dispute the need to add one if the right-most light is on. And without loss of generality I would assume the left-most light can always be left off and the alternating pattern we are aiming for be XOXOXOXO where X is off and O is on.
My definition of the transition number would be "Ignoring the first light, count the number of other lights which have a different on-off parity to the light on their immediate left." Example: XXOOXOOO would have a transition number of 3. (The third, fifth and sixth light are different to the light on their left.) The initial state XXXXXXXX has a transition number of 0 and the final state XOXOXOXO has a transition number of 7.
When a block of lights are changed, each light will remain the same parity as its left neighbour except for the first in the block and the light to the immediate right of the block. Example: XXO(OXOO)O would only cause the fourth and eighth light to change with respect to its left neighbour. So XXO(OXOO)O (transition number 3) would become XXO(XOXX)O (transition number 5). The largest possible increase in the transition number is +2. To get from 0 to 7 therefore requires at least 4 moves.
X(XXXXX)XX (tn 0) becomes X(OOOOO)XX (tn 2)
XOOOOOX(X) becomes XOOOOOX(O) (tn 3)
XO(OOO)OXO becomes XO(XXX)OXO (tn 5)
XOX(X)XOXO becomes XOX(O)XOXO (tn 7)
Log in to reply
The instruction "add one if the last light is on" should be removed.
The instruction "add one if the last first light is on" can be removed if the desired final state may be on-off-on-off-etc. The problem states "alternating off-on", so assumed that the first bulb had to be off.
really nicely explained!
Remove the light bulb from the left as it should remain off and since being in a corner including it in a long chain press would be meaningless. We are left with 7 bulbs and desired condition is 4 alternate bulbs should be on. This means 3 alternate inner bulbs should be off. so if we could switch those three on in less than three steps then we would press all seven together to get desired output in less that 4 total steps. Now consider those 5 bulbs containing those three 3 closed bulbs and repeat the same logic as above, this time we are required to switch on two alternate bulbs with one press only which is not possible and hence through induction the answer is no
Very cute.
But according to your solution, we are assuming that in the 7-light bulbs case, the end ones have to be in the same state(either on or off) at every instant of the problem. But that might not always hold, right? So, maybe there is some solution which doesn't assume this. The extreme ones can light up independently of each other? Please correct me if I am wrong.
The least you can do is 4 steps because there are 4 light bulbs that are needed to be turned on. If we do rows, then lights will be turned off and on at the same time. This means you will need to do more steps. So the least is 4.
Good answer
I'm sorry, but this is not answering why 4 is the least... If my target is NNFFFFNN (N=on, F=off), then I want to turn on 4, but I need just 2 moves...
they mean 4 alternate ones
Count the number of changes - that is, the number of times as you move from left to right the state changes from off to on or vice versa. The initial position has no changes, and the target position has seven. Each move can add at most two changes, for obvious reasons. Therefore if you make no more than three moves, there can be no more than six changes.
My explanation might be not so well.
Here is what I got -
Since in the above problem , alternate bulbs have to be turned ON, and our methodology involves picking consecutive bulbs and turning them ON. This implies we cannot ON two alternate bulbs simultaneously since we are selecting adjacently. Hence , the total number of steps will be equal to total number of bulbs to be turned ON.
In this case , 4
Hence , A N S W E R = N o
Count how many lights are opposite of the light immediately to the left; add one if the first light is on. Call this the transition number .
In the initial state, the transition number is zero.
In the final state, the transition number is eight.
In each move, the transition number can be increased at most by two. (It can change by -2, 0, or +2.)
Therefore it will take at least 8 / 2 = 4 moves to accomplish the task.