Big hint: Hfr hygensvygref.
Jul. 31st, 2007 10:27 pmCool problem Babai gave us: We have n 3-state switches, where n is not necessarily finite, controlling a 3-state lightbulb[0]. This function has the property that if we change the position of every single switch, the output changes. Show that if n is finite, the output must be determined entirely by a single switch (a "dictator switch"), but that if n is infinite, this is not necessarily so. (Yes, n is nonzero.)
[0]Yes, a 3-state lightbulb. It can be red, green, or blue, but it never turns off. More realistically, it could be off, full-power, or half-power. Or mabye it's a motor which is on, forward, or reverse. Or maybe it's just an abstract set of 3 elements and we really don't care what it represents, because nobody would ever come up with such a ridiculous control scheme. After all, the point of the problem is to show that in the finite case, all but one of the switches are in fact absolutely useless, while the infinite case is simply physically impossible.[3]
[3]Yes, I added these footnotes in response to Wai Lee's comment.
[0]Yes, a 3-state lightbulb. It can be red, green, or blue, but it never turns off. More realistically, it could be off, full-power, or half-power. Or mabye it's a motor which is on, forward, or reverse. Or maybe it's just an abstract set of 3 elements and we really don't care what it represents, because nobody would ever come up with such a ridiculous control scheme. After all, the point of the problem is to show that in the finite case, all but one of the switches are in fact absolutely useless, while the infinite case is simply physically impossible.[3]
[3]Yes, I added these footnotes in response to Wai Lee's comment.
