Solving Bulbs & Buttons: Proving All ON at Same Time

  • Thread starter engin
  • Start date
In summary, we have n bulbs and n buttons connected to each other with a box. Whenever a button is switched, the connected bulb changes its state from ON to OFF or vice versa. Each button is connected to its corresponding bulb, and can also be connected to other bulbs. Additionally, if a button is connected to a bulb, that bulb is also connected to the button. Given that all bulbs are initially OFF, it can be proved by induction that there exists an order in which all bulbs can be switched on simultaneously. This is possible because the bulbs and switches can be split into groups that can be independently switched on and off, and a subgraph can be formed with the remaining switches and bulbs to satisfy the condition. The starting condition
  • #1
engin
8
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
  • #2
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
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
 

1. How do you solve the "Bulbs & Buttons" problem?

The "Bulbs & Buttons" problem can be solved by using a systematic approach. First, label each bulb and button with a number. Then, start with all buttons off and flip the first button. Observe which bulbs turn on and off. Repeat this process for each button, keeping track of which bulbs are affected. Finally, analyze the patterns and determine the combination of buttons that will result in all bulbs being on.

2. What is the purpose of the "Bulbs & Buttons" problem?

The purpose of the "Bulbs & Buttons" problem is to demonstrate the concept of Boolean logic and how it can be applied in solving problems. It also helps to develop critical thinking and problem-solving skills.

3. What is the significance of proving all bulbs to be on at the same time?

In real-world applications, the "Bulbs & Buttons" problem can represent a scenario where multiple conditions need to be met for a desired outcome. By proving that all bulbs can be turned on simultaneously, it shows that all necessary conditions have been satisfied.

4. Are there any shortcuts or tricks for solving the "Bulbs & Buttons" problem?

While there is no specific shortcut for solving the problem, some tips that can help include starting with the button that affects the most number of bulbs, looking for patterns in the results, and breaking down the problem into smaller parts if needed.

5. Can the "Bulbs & Buttons" problem be solved using a different approach?

Yes, there are multiple ways to solve the "Bulbs & Buttons" problem. Some people may use a trial and error method, while others may prefer to create a truth table or use Boolean algebra. The most important thing is to understand the underlying logic and find a method that works best for you.

Similar threads

MHB Sum of basis elements form a basis
    • Linear and Abstract Algebra
Replies
4
Views
1K
Adding increasing fractions without averaging numerators
    • General Math
Replies
1
Views
1K
B Inverse Transformation from Response Surface
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
736
Vectors as geometric objects and vectors as any mathematical objects
    • Linear and Abstract Algebra
Replies
27
Views
1K
I Two basic results from measure theory -- on volumes of rectangles
    • Topology and Analysis
Replies
2
Views
128
Isolate solar charger PWM pulses
    • Electrical Engineering
Replies
10
Views
859
MHB Carry select adder - Time calculation
    • Programming and Computer Science
Replies
1
Views
672
I Proving Isometries: A Step-By-Step Guide
    • Linear and Abstract Algebra
Replies
3
Views
1K
B Can Info Travel FTL? Understanding Speed of Information
    • Special and General Relativity
Replies
6
Views
1K
Best multiple/many individual MOSFET driver IC?
    • Electrical Engineering
Replies
33
Views
5K

Hot Threads

Recent Insights

Back
Top