Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have specified number of light bulbs. In addition to the array there are buttons. Pressing the button changing state of light bulbs which are connected to the switch. It is known that for each set of lamps exist button that is connected with the odd-number of bulbs from this set. Prove that properly pressing the buttons we can turn off all bulbs.

Very nice task, but hard. I think that I can make a $Z^n$ space of bulbs, but how to prove that we have a basis of it? Or that's not a correct way?

I'm looking for hints.

share|improve this question
1  
Can you explain what you mean by " It is known that for each set of lamps are connected with the odd-number of bulbs." –  Calvin Lin Jan 9 '13 at 9:59
    
Yes, that was the case –  Jonny Jan 9 '13 at 10:13
1  
Let me describe. For each non-empty set of bulbs, we have a set of buttons which are connected with odd number of bulbs from this set. –  Jonny Jan 9 '13 at 10:35
    
Are you familiar with vector spaces over finite fields (such as the integers mod 2)? –  Erick Wong Jan 9 '13 at 10:36
    
Yes. I'm familiar with linear spaces over finite/infinite fields. –  Jonny Jan 9 '13 at 10:39
add comment

1 Answer

up vote 3 down vote accepted

Hint: The "odd number of bulbs from a set" can be rephrased in terms of a dot product over $GF(2)$. If there were a non-empty set of bulbs with even-sized connections to all buttons, this would give you a non-zero vector in the nullspace of a certain matrix...

More hints: If you fix an ordering of the bulbs and represent any set of bulbs as a $\{0,1\}$-vector, then the dot product of two vectors (each representing a set) is equal to the size of the intersection of the corresponding two sets. In particular, modulo $2$, this dot product is zero or non-zero according to whether the intersection is odd or even.

share|improve this answer
    
How is definied GF(2)? –  Jonny Jan 9 '13 at 11:54
1  
I don't follow, can you please some more details ? –  Belgi Jan 9 '13 at 12:59
1  
@Jonny $GF(2)$ is one of the names for the finite field of integers modulo $2$. You might have seen it denoted $\mathbb F_2$ or $\mathbb Z/2\mathbb Z$, for instance. –  Erick Wong Jan 9 '13 at 18:25
    
Thank You for explanation. –  Jonny Jan 9 '13 at 23:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.