Friday 11 April 2008

Too many Lamp Lighters

Yesterday, as on every Thursday, Manchester University's geometers, mathematical physicists and topologists gather for the Geometry Seminar. The talk itself was a really great proof of the Mischenko-Fomenko conjecture about the existence maximal complete commutative subalgebras of finite dimensional Lie algebras. Alexei Bolsinov gave a geometric proof of one of the subcases of the proof using some quite neat parts of the theory.

As per usual, we decamped to the pub afterward to discuss anything and everything. Soon enough, one of my supervisors started posing interesting little mathematical problems. Here is one which "of course, the school children know how to solve" which occupied a some minutes in an otherwise boring sleepless night.
Suppose there are a hundred push-button lamps and a hundred blind lamplighters. All lamps are initially off. The first lamplighter passes along the row and pushes each button in turn thereby turning every lamp on. The second lamplighter passes along the row afterward and pushes every other button regardless of whether the lamp is on or off. (So now all the even numbered lamps are off.) The third lamplighter passes along the row and pushes every third button, the fourth pushes every fourth button and so on. After all of the hundred lamplighters have passed by, which of the lamps remain lit?
For the answer and an explanation, see tomorrow.

No comments: