Solving Bulbs & Buttons: Proving All ON at Same Time

  • Thread starter Thread starter engin
  • Start date Start date
AI Thread Summary
The discussion focuses on proving that n bulbs can all be turned ON simultaneously using n buttons, where each button toggles its connected bulb and potentially others. The key insight is that if a button is connected to another bulb, the connection is mutual, allowing for independent groups of bulbs and buttons to be formed. By using induction, it is shown that switching one button can activate multiple bulbs, while a subgraph of remaining buttons and bulbs can also be manipulated to achieve the same result. The proof begins with the simplest case of n=1 and extends to larger groups. Ultimately, the argument demonstrates that a sequence exists to turn all bulbs ON at the same time.
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
 

Thread 'Finding the number of ways to arrange identical balls in a circle (3 different colors)'

I tried to combine those 2 formulas but it didn't work. I tried using another case where there are 2 red balls and 2 blue balls only so when combining the formula I got ##\frac{(4-1)!}{2!2!}=\frac{3}{2}## which does not make sense. Is there any formula to calculate cyclic permutation of identical objects or I have to do it by listing all the possibilities? Thanks
View full post »

Thread 'Greatest possible value of a constant in polynomial'

Since ##px^9+q## is the factor, then ##x^9=\frac{-q}{p}## will be one of the roots. Let ##f(x)=27x^{18}+bx^9+70##, then: $$27\left(\frac{-q}{p}\right)^2+b\left(\frac{-q}{p}\right)+70=0$$ $$b=27 \frac{q}{p}+70 \frac{p}{q}$$ $$b=\frac{27q^2+70p^2}{pq}$$ From this expression, it looks like there is no greatest value of ##b## because increasing the value of ##p## and ##q## will also increase the value of ##b##. How to find the greatest value of ##b##? Thanks
View full post »

Similar threads

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

Hot Threads

Recent Insights

Back
Top