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.

  • 1
    $\begingroup$ Can you explain what you mean by " It is known that for each set of lamps are connected with the odd-number of bulbs." $\endgroup$ – Calvin Lin Jan 9 '13 at 9:59
  • $\begingroup$ Yes, that was the case $\endgroup$ – Jonny Jan 9 '13 at 10:13
  • 1
    $\begingroup$ 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. $\endgroup$ – Jonny Jan 9 '13 at 10:35
  • $\begingroup$ Are you familiar with vector spaces over finite fields (such as the integers mod 2)? $\endgroup$ – Erick Wong Jan 9 '13 at 10:36
  • $\begingroup$ Yes. I'm familiar with linear spaces over finite/infinite fields. $\endgroup$ – Jonny Jan 9 '13 at 10:39

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.

  • $\begingroup$ How is definied GF(2)? $\endgroup$ – Jonny Jan 9 '13 at 11:54
  • 1
    $\begingroup$ I don't follow, can you please some more details ? $\endgroup$ – Belgi Jan 9 '13 at 12:59
  • 1
    $\begingroup$ @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. $\endgroup$ – Erick Wong Jan 9 '13 at 18:25
  • $\begingroup$ Thank You for explanation. $\endgroup$ – Jonny Jan 9 '13 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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