Author |
Topic: All lights on puzzle (Read 3656 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
All lights on puzzle
« on: Sep 24th, 2004, 8:40am » |
 Quote  Modify
|
Here is an interesting problem which is sort of related to the Communist graph problem mentioned by baudolino in the 'Socialist graph' thread.
You have a set of n bulbs and n switches. Switch i controls a fixed set of bulbs Bi. Each set Bi satisfies the following: (For convenience, asssume the bulbs are numbered 1 to n too)
1) i [in] Bi
2) j [in] Bi if and only if i [in] Bj
Initially all bulbs are off. Show that by toggling some set of switches one can turn on all the bulbs.
|
|
 IP Logged |
|
|
|
baudolino
Guest
|
In terms of graphs, the problem becomes:
G graph. Let A be the adjacent matrix associated to G. Consider the matrix I+A, where I is the identity matrix. Prove that there is a subset of rows such that the sum of the rows (as a vector with entries in Z/2Z) is the vector (1,1,1,...,1).
Without loss of generality, G can be assumed connected.
The problem follows immediately if I+A is nonsingular in Z/2Z.
I did not get anywhere when I+A is singular ( exactly when -1 is a graph eigenvalue).
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: All lights on puzzle
« Reply #2 on: Sep 25th, 2004, 1:36pm » |
Quote Modify
|
on Sep 24th, 2004, 8:10pm, baudolino wrote:In terms of graphs, the problem becomes:
Without loss of generality, G can be assumed connected.
The problem follows immediately if I+A is nonsingular in Z/2Z.
I did not get anywhere when I+A is singular ( exactly when -1 is a graph eigenvalue). |
|
Yes. We need to show that there is some x such that x + Ax = J where J = a column of all 1's. It is an interesting approach and I am sure a proof using Linear Algebra can be found.
There is also a non-Linear Algebra proof of this.
I think this problem is equivalent to the Communist graph problem, with initial values all 0 and final values all 1.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: All lights on puzzle
« Reply #3 on: Sep 25th, 2004, 6:08pm » |
Quote Modify
|
Here is a Linear Algebra proof of this due to Noga Alon.
:
First some definitions and theorems.
Let V be a vector space over a field [bbf]. (Assume it is actually a subspace of a larger space)
Define Ortho(V) to be the set of all vectors orthogonal to each vector of V.
i.e Ortho(V) = {x | xTy = 0, [forall] y [in] V}
It can be shown that
Theorem1: if W = Ortho(V), then V = Ortho(W).
(I won't prove this here).
This implies the following.
Corollary1: If a [notin] V, then there is a vector w orthogonal to each element of V but not orthogonal to a.
(V is a sub space of a larger vector space)
Proof: Follows easily from Theorem 1.
Note that the above is valid for any field.
From now on the field is [bbf]2.
Let A be a symmetric NxN matrix. Let the ijth entry be aij. Consider the diagonal of A,
d = (a11,a22,...,aNN)
For any vector v, we have that
vTAv = dTv. (since r2 = r and r + r = 0 in [bbf]2)
Let [bbr](A) be the space spanned by the rows of A.
Proposition1: d [in] [bbr](A).
Proof: Assume d [notin] [bbr](A). Then by Corollary1 of Theorem 1, we have that there is some w orthogonal to the rows of A but not to d. For this w, Aw = 0.
Now wTAw = dTw. Since Aw = 0, we have that RHS is also 0, i.e d is orthogonal to w.
Contradiction. Hence d [in] [bbr](A).
In the case of our problem, d is (1,1,....,1).
All can I say about this proof: WOW! 
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: All lights on puzzle
« Reply #4 on: Sep 26th, 2004, 2:53pm » |
Quote Modify
|
Here is a hint for a proof which does not use Linear Algebra.
:
First prove the following result:
G is a connected graph. Let V(G) be the vertex set of G.
Show that V(G) can be decomposed into two disjoint sets V1 and V2 such that:
i) [forall] x [in] V1, the cardinality of S = {y| y [in] V1 and (x,y) is an edge of G} is even.
ii) [forall] x [in] V2, the cardinality of S = {y| y [in] V2 and (x,y) is an edge of G} is even.
i.e V1 and V2 each span even degree subgraphs of G.
Note: we don't care about the edges going from V1 to V2
The above result can be proved by using Linear Algebra too!
:
|
|
IP Logged |
|
|
|
baudolino
Guest
|
1st proof is nice. Very nice.
Maybe because I usually avoid Z/2Z, theorem 1 was not trivial to me. The theorem follows from the dimension equality dim V + dim V [perp] = dim U, where V [subseteq] U. The equality follows if you consider the composition i* [circ] B, where B : V ---> V* is the isomorphism induced by the nondegenerate bilinear form, i* : V* ---> U* is the dual of the inclusion i : U ---> V, and [circ] is the composition sign. The function i* [circ] B is surjective and its kernel is U[perp], so the equality follows from the usual dim (kernel f) + dim(image f) = dim(domain f).
My initial failed attempt was to prove theorem 1 directly, through a study of the nonedegenerate symmetric bilinear forms over Z/2Z. Given such a form B over U and a subspace V [subseteq] U, I tried to look for a normal form for B relative to a base of vectors of U that extends a base of vectors of V. I quickly got into trouble when the restriction of the form B to V is degenerate (exactly when V [cap] V[perp] is nonempty). The most interesting examples are when B is a symmetric nonsingular matrix with 0s on the diagonal. What is the normal form of such matrices B? Such matrices are equivalent (via adjacent matrices) to graphs. If B and B' are two such similar matrices, what is the relation between their associated graphs? What is the relation between the graph associated to B and the graph associated to its normal form?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: All lights on puzzle
« Reply #6 on: Sep 27th, 2004, 8:06pm » |
Quote Modify
|
on Sep 27th, 2004, 7:11am, baudolino wrote:1st proof is nice. Very nice.
Maybe because I usually avoid Z/2Z, theorem 1 was not trivial to me. The theorem follows from the dimension equality dim V + dim V [perp] = dim U, where V [subseteq] U.
|
|
Isn't dim(V) + dim(V[perp]) = dim(U) valid for any finite field? I don't think there is anything special about [bbf]2.
Sorry, I don't know much about Bilinear forms, the book I have discusses only real spaces. I will have to search for one which discusses an arbitrary field. Some of the theorems valid for real spaces are not valid for finite fields. For instance, V [cap] V[perp] = {0} is valid for real spaces, but need not be true for spaces over finite fields.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: All lights on puzzle
« Reply #7 on: Sep 29th, 2004, 3:30pm » |
Quote Modify
|
Is this thread dead? 
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: All lights on puzzle
« Reply #8 on: Oct 21st, 2004, 8:45pm » |
Quote Modify
|
Alright, before this thread passes away, here is a solution which does not use Linear Algebra.
The Hint was:
First prove the following result:
G is a connected graph. Let V(G) be the vertex set of G.
Show that V(G) can be decomposed into two disjoint sets V1 and V2 such that:
i) [forall] x [in] V1, the cardinality of S = {y| y [in] V1 and (x,y) is an edge of G} is even.
ii) [forall] x [in] V2, the cardinality of S = {y| y [in] V2 and (x,y) is an edge of G} is even.
Let us see how this hint helps in proving what we want.
We can map our problem to:
Given a graph G. Initial values of vertices are 0. We can pick a vertex and flip (0 to 1, 1 to 0) the values of that vertex and its neighbours. Is it possible to make all vertices 1?
So for turning on all the lights, we are looking for a subset X of the vertices of the graph such that, every vertex not in X is incident to an odd number of vertices of X and every vertex in X is incident to an even number of vertices of X.
Here is how we can use the hint result. To every vertex of even degree of G, add an edge to a new vertex N (N is same for all) to get G'. This makes all the vertices of G' of odd degree. By the result of the hint, this graph has a partition into two sets X and Y such that any vertex in X is incident to and even number of vertices of X. Any vertex in Y is incident to an even number of vertices in Y.
Suppose N is in Y. Consider X. every vertex in X is incident to an even number of vertices in X. Every vertex in Y is incident to an odd number of vertices in X. So that is what we wanted!
Note, we don't care about N.
Here is one way of proving the hint.
We prove by induction in the number of vertices of G.
Base cases are trivial.
Suppose we are given G(V,E) with n+1 vertices. Suppose G has all vertices of even degree. Then we are done by taking X = V and Y = [phi].
So suppose there is a vertex o, which is of odd degree.
Let o1, o2,..., ok be the neighbours of o in G. Consider the graph G' which is formed as follows. if oi and oj have an edge in G. delete that. if oi and oj are not adjacent, join them by an edge.
Delete o.
Apply induction hypothesis on G'. Say we get X and Y.
o must be incident (in G) to an even number of vertices in one of X or Y, say X. Add o to X. Delete the edges which we had added between neighbours of o and add back the edges which we had deleted.
It is not difficult to show that this partition: X U {o} and Y is what we are looking for.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove