1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Bulbs and Buttons

  1. Jul 27, 2007 #1
    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?
  2. jcsd
  3. Jul 27, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    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?
  4. Jul 30, 2007 #3
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook