Solving Bulbs & Buttons: Proving All ON at Same Time

  • Thread starter Thread starter engin
  • Start date Start date
Click For Summary
SUMMARY

The discussion focuses on proving that all bulbs can be turned ON simultaneously using a series of switches, given the specific connectivity between bulbs and buttons. Each button b_i is connected to its corresponding bulb B_i and potentially other bulbs, creating a symmetrical relationship. The proof utilizes induction and graph theory, specifically examining the subgraph formed by the remaining switches and bulbs after one is activated. The conclusion asserts that there exists a sequence of operations that allows all bulbs to be ON at the same time.

PREREQUISITES
  • Understanding of graph theory concepts, particularly subgraphs and vertex connections.
  • Familiarity with mathematical induction as a proof technique.
  • Knowledge of equivalence classes and their applications in combinatorial problems.
  • Basic concepts of bulb-switch systems and their operational mechanics.
NEXT STEPS
  • Study advanced graph theory, focusing on connectivity and independence in graphs.
  • Explore mathematical induction in depth, particularly in combinatorial proofs.
  • Research equivalence relations and their implications in network problems.
  • Examine similar problems in combinatorial optimization and their solutions.
USEFUL FOR

This discussion is beneficial for mathematicians, computer scientists, and anyone interested in combinatorial logic and graph theory applications, particularly in systems involving switches and bulbs.

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?
 
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
 

Similar threads

MHB Sum of basis elements form a basis
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad No structure in ##(d,x)## in ##\textbf{Met*}(X)## is admissible
  • · Replies 0 ·
Replies
0
Views
2K
Graduate Adding increasing fractions without averaging numerators
  • · Replies 1 ·
Replies
1
Views
2K
High School Inverse Transformation from Response Surface
  • · Replies 1 ·
Replies
1
Views
1K
Proving Non-Empty Set Theory Equations: A Solution Using Induction Method
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Vectors as geometric objects and vectors as any mathematical objects
  • · Replies 27 ·
Replies
27
Views
2K
Undergrad Proving Isometries: A Step-By-Step Guide
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Two basic results from measure theory -- on volumes of rectangles
  • · Replies 2 ·
Replies
2
Views
3K
Best multiple/many individual MOSFET driver IC?
  • · Replies 33 ·
2
Replies
33
Views
6K
High School Can Info Travel FTL? Understanding Speed of Information
  • · Replies 6 ·
Replies
6
Views
2K