For the Dim Bulbs
After the (n+1)st Sangria spill on your dirty shag rug, and after learning on good authority that wasabi green is officially hip, you've resolved: it's home improvement time.
You rustle up a few pals and get to work, and a few hundred dollars later the place is looking like less of a dive, but in a moment of belated clarity you realise that only one thing needed to be changed to cement its 'cool' status:
just install 'The Clapper' in every room in the house.
For those too young to remember the Clapper heyday, this device controls the on/off switch to a lighting source, and toggles its position when you clap in the audible range--which, for added value and amusement, tends to extend at least into adjacent rooms. For our purposes, let's say the device's range is exactly its host room and those directly adjacent. So, say you've got one light source per room, each with a Clapper, in a house which, like any good house, is actually just an m-node undirected graph.
Now, for your grand house-rewarming party, you invite all your friends over, wait until their thinking skills are nice and clouded, and issue a challenge: clap the house into a fully-lit state.
In fact, no matter what your house's structure, this challenge can always be met, as long as lights are initially off! Can you prove it?
I came up with this result a few years ago after playing a computer solitaire game, which presented this problem for a 5-by-5 square grid (don't recall if there were diagonal connections... anyone have a weblink?). Thought I was pretty clever, but then I saw it given as a problem in an old math journal, I think an AMS one (I'll post a ref if I ever find it). No fancy tools needed to solve this fairly simple puzzle, although of course some linear algebra would help.
Extra Credit: Now the lights all have k > 2 brightness settings, which you cycle thru with claps. Prove it's possible to get them all to the brightest setting. Extra credit, think of a less hasty and more true generalization.
Extra Extra Credit: Now some of the lights are off/bright, while some are off/dim/bright. Now it's no longer always possible to get all lights bright simultaneously. In fact, I'm guessing it's NP-complete to maximize the number of bright lights, but haven't proved this. What's the story?
Oh, and the wasabi-green tip came to my attention (briefly!)in a recent New Yorker.
You rustle up a few pals and get to work, and a few hundred dollars later the place is looking like less of a dive, but in a moment of belated clarity you realise that only one thing needed to be changed to cement its 'cool' status:
just install 'The Clapper' in every room in the house.
For those too young to remember the Clapper heyday, this device controls the on/off switch to a lighting source, and toggles its position when you clap in the audible range--which, for added value and amusement, tends to extend at least into adjacent rooms. For our purposes, let's say the device's range is exactly its host room and those directly adjacent. So, say you've got one light source per room, each with a Clapper, in a house which, like any good house, is actually just an m-node undirected graph.
Now, for your grand house-rewarming party, you invite all your friends over, wait until their thinking skills are nice and clouded, and issue a challenge: clap the house into a fully-lit state.
In fact, no matter what your house's structure, this challenge can always be met, as long as lights are initially off! Can you prove it?
I came up with this result a few years ago after playing a computer solitaire game, which presented this problem for a 5-by-5 square grid (don't recall if there were diagonal connections... anyone have a weblink?). Thought I was pretty clever, but then I saw it given as a problem in an old math journal, I think an AMS one (I'll post a ref if I ever find it). No fancy tools needed to solve this fairly simple puzzle, although of course some linear algebra would help.
Extra Extra Credit: Now some of the lights are off/bright, while some are off/dim/bright. Now it's no longer always possible to get all lights bright simultaneously. In fact, I'm guessing it's NP-complete to maximize the number of bright lights, but haven't proved this. What's the story?
Oh, and the wasabi-green tip came to my attention (briefly!)in a recent New Yorker.
Labels: general math, puzzles
posted by Andy D at
8:24 PM
11 Comments:
It seems to me that your Extra Credit and your Extra Extra Credit are in contradiction. Suppose we are given a house with 2-step and 3-step bulbs. Then take the same house and place 6 step bulbs in each room. According to your Extra Credit result, there should be a sequence of claps which turns all the 6 step bulbs to their highest level. But then this sequence would also turn the 2 and 3 step bulbs to their highest level.
In fact, now that I think about it, your Extra credit isn't even true when k is prime. Consider a house with 4 rooms, bordering each other in a ring, and take k=3.
DavidSpeyer
By
Anonymous, at 5:13 PM
Oh, PS the original puzzle is correct, and is very elegant. Proof for those who know linear algebra:think of the lit/unlit states of the house as vectors over the field with two elements (unlit=0). For each room r, we'll right v_r for the vector which has a 1 in position s if room s is adjacent to r. The achievabe states form a vector subspace, specifically the span of the v_r. If the all 1's state isn't in this subspace, then there is some vector w which is orthogonal to all the v_r, but not to the all 1's vector. Let H be the induced subgraph of G whose vertices are the rooms which have ones in the corresponding coordinates of w. Then, by pairing w against v_r for r in H, we see that every vertex of H has odd degree. By pairing w with the all ones vector, we see that H has an odd number of vertices. But the sum of all the degrees of vertices in H must be even, a contradiction.
DavidSpeyer
By
Anonymous, at 5:19 PM
Thanks, David. Apologies all, that E.C. was an afterthought that I checked but not well enough.
My proof of the k=2 result (which I'll also have to check) was different, using induction and the structure of Gaussian elimination. But yours is nicer.
By
Andy D, at 8:33 PM
Funny how many technological advances were invented by the Orthodox to get around laws... You should also do a puzzle about how many floors the shabbos elevator must stop at, how the spark-free carburetor works, etc.
By
Anonymous, at 3:21 AM
Funny how many technological advances were invented by the Orthodox to get around laws
Actually, turning a light on in Shabbat is a no-no for an Orthodox Jew, even if he uses a clapper. It's even not allowed to ask another Jew to turn the light on. The one thing that is allowed is to ask a Gentile to do it. That's the famous "Shabbat Gentile"
By
Anonymous, at 3:48 PM
Andy, the riddle you describe in your post is called the "Lights Out" problem. That's also the name of the electronic puzzle game that you described (you played a computer version of it). Here is a web page with an amazing amount of information on Lights Out.
Here is a game somewhat in similar spirit to Lights Out, which was originally solved by Hannenhalli and Pevzner (I call them H-P from now on) in 1995. This game is related to an important problem in computational biology. Like Lights Out, the H-P game also has some linear-algebraic flavor, but the only known solution uses a somewhat messy induction, and is long and not very intuitive. If you can find a solution which is either (i) simple, or (ii) intuitive, or (iii) algebraic, that would be interesting to a lot of people. Also, there is a generalization with a 64$ reward for solving it. Contact me for more details.
Here is the game: You start with a connected graph, where each node has a light, turned either on or off. At least one of the lights is off.
You are allowed to clap only inside of an unlit node. When you clap inside an unlit node v, the lights in the adjacent nodes switch their status from lit to unlit, or vice versa. But when you clap inside v, the structure of the graph also changes: for every two nodes u,w which are neighbors of v, if there was an edge between u and w then it is removed, otherwise it is created. v is considered a neighbor of itself, so when you clap inside v, it becomes lit and isolated. The objective of the game is to turn all nodes to lit and isolated.
The H-P theorem states that this game is always solvable. The game above has a linear-algebraic formulation (think of the adjacency matrix of the graph when an unlit node puts 1 in the appropriate entry on the main diagonal, and see what a clapping operation does to the matrix). However, the H-P proof does not use the linear algebraic formulation. It is a somewhat messy induction on a certain "goodness parameter" of the graph.
If you can find a linear algebraic proof of the H-P theorem, then this is not only nice in itself, but it can solve some major open problems in computational biology. (more about that in my paper Matrix Tightness: A Linear-Algebraic Framework for Sorting by Transpositions with Tzvika Hartman.
By
Anonymous, at 4:28 PM
Wow--thanks, Elad! Pevzner's at UCSD, maybe I'll ask him about the H-P game sometime.
I have been told that some observant Jews consider Clapper use on Shabbat OK. However, as much as I would be pleasantly surprised to see my blog host Halakhic disputes, I don't feel personally qualified to contribute... :)
By
Anonymous, at 6:21 PM
PS, thanks for the pointer to a great site on Light's Out... it has a Javascript 5x5 version, for anyone who wants the maddening thrill of the real thing.
By
Anonymous, at 6:32 PM
Recommended reading that eluded the best-seller lists:
"The Shabbos Goy: A Study in Halakhic Flexibility."
: )
By
Anonymous, at 7:43 PM
Perhaps it's getting old now, but I couldn't resist; and it just struck me as so *relevant*:
http://www.youtube.com/watch?v=mvWdkz8Ra54
By
Anonymous, at 6:38 PM
:)
By
Anonymous, at 2:45 AM
Post a Comment
<< Home