# Homework Help: Bulbs and Buttons

1. Jul 27, 2007

### engin

We have n bulbs (B_1,B_2,...,B_n) and n buttons(b_1,b_2,...,b_n) connected to each other with a box. Whenever we switch a button, the condition of the bulb which is connected to the button changes;that is, if it was ON before, now it is OFF, or vice versa. We know that each b_i button - (i=1,...,n) - is connected to the B_i bulb, but additionally it can be connected to other bulbs. Besides, if b_i is connected to B_k, then b_k is connected to B_i. So if all bulbs are OFF at the beginning, prove that there exists an order in which they become ON at the same time.

"Besides, if b_i is connected to B_k, then b_k is connected to B_i." Is it somehow related to parity?

2. Jul 27, 2007

### Dick

No, not parity. Looks more to me like an equivalence class problem. Can you show that you can split the bulbs and switches into groups which can be switched on and off independently?

3. Jul 30, 2007

### balakrishnan_v

It can be proved by induction.
Consider any vertex i. Let it be connected to k other vertices in the bulbs section.
If you switch vertex i, we switch on k bulbs.
Consider the subgraph H formed by the other n-k switches and n-k bulbs.
Since this subgraph also satisfies the condition that each switch is connected to its corresponding bulb,there exists a sequence in H that allows to switch on all the n-k bulbs.
This completes the proof.

The elementary starting condition is n=1