Big hint: Hfr hygensvygref.

[sniffnoy]

Cool 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.

Comments

[ramennoodle463.livejournal.com]

output is one of the three states?

[sniffnoy.livejournal.com]

Um... the output has 3 states. What you have is a function f:{0,1,2}ⁿ→{0,1,2}. That the output set is the same as one of the inputs is not really relevant - how are you going to iterate it? You can only directly iterate it for n=1, and that case doesn't even need proving. For n>1 - say n=2 - you'd have to do something like f(f(x,y),f(z,w)). If you can get that to work, go ahead, but...