Can All Bulbs Be On?

Probability Level 5

Let $n$ be a positive integer $\leq 1000.$ Suppose $n$ bulbs are arranged in a row. Initially the first bulb is switched on and all other bulbs are switched off. Each second, we change the states of the bulbs according to the following rules:

If the state of a bulb is identical to the state of all its neighbors (one neighbor for the bulbs at the edges, two neighbors for the other bulbs), it is switched off.
Otherwise, it is switched on.

It turns out that eventually (after a finite amount of time) all bulbs are switched on. Find the largest possible value of $n.$

Details and assumptions

The state of a bulb refers to whether it is switched on or off.
This problem is inspired by ISL 2006 C1 .

The answer is 512.

2 solutions

Samuraiwarm Tsunayoshi
Aug 20, 2014

Not a full solution, but might help you think about the problem.

1000000000000000 *
1100000000000000 *
0110000000000000
1111000000000000 *
0001100000000000
0011110000000000
0110011000000000
1111111100000000 *
0000000110000000
0000001111000000
0000011001100000
0000111111110000
0001100000011000
0011110000111100
0110011001100110
1111111111111111 *
1:on & 0:off

The figure clearly shows the half of Sierpinski triangle .

I claim that the bulbs that all light can only be the form of $2^{n}$ for some $n$ .

Therefore, the answer should be $\boxed{512}$ . ~~~

See http://www.artofproblemsolving.com/Forum/viewtopic.php?p=874978&sid=b7a0ef2f49e38ed70d6efd96ee8ae411#p874978

Happy Melodies - 6 years, 9 months ago

Mohit Bhat
May 12, 2014

Since, this problem requires adjacent bulbs for getting the condition of a particular bulb in the next step. Hence, the following condition prevails each time first and its succeeding bulbs are ON without a single one in between being OFF.

Condition which shall always be true for all bulbs in ON condition:

The number of bulbs is $n=2^{m}$ , where m is an integer.

And since n is less than or equal to 1000, this implies m is less than or equal to 9.

Keeping the condition of largest n in mind, $n=2^{9}=512$ .

Thus, the largest number of bulbs arranged in a row according to the given condition is $n=\boxed{512}$

Why exactly must $n$ be a power of $2?$

Sreejato Bhattacharya - 7 years, 1 month ago

What I found is that it can be proven that it holds for any power of 2 and for any other value it can be disproved by induction by breaking the arrangement into pieces......

Eddie The Head - 7 years ago

Can you show how?

Nathan Ramesh - 7 years ago

Bhattacharya, this problem has some common points with my problem, you can discover it and find the way to answer your question!

Dang Anh Tu - 7 years ago

I'm new here, but how exactly is this level 4? It was pretty easy for me.

Edoardo Annunziata - 6 years, 12 months ago

Ca you prove that all $n=2^m$ works and no other $n$ works? The bulk of the problem is proving that your answer is correct. Finding the answer isn't hard.

This is also why I thought this problem would have been better if it was a note instead.

Daniel Liu - 6 years, 12 months ago

Can All Bulbs Be On?

The answer is 512.

2 solutions

0 pending reports