Solving Bulbs & Buttons: Proving All ON at Same Time

  • Thread starter Thread starter engin
  • Start date Start date
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
2 replies · 3K views
engin
Messages
8
Reaction score
0
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.

Okay, i have some ideas about this but don't know how to use the information
"Besides, if b_i is connected to B_k, then b_k is connected to B_i." Is it somehow related to parity?
 

Discussion

Physics news on Phys.org
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?
 
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