[bushindo]

Let's say that you are setting the dining table for a party of 64 guests. The 64 guests will be seated at a giant circular table. Each seat has a lamp, and currently some of the 64 lamps are on and some are off. The butler offers to play a game with you. Let's say that the chairs are labelled with the guests names, which for convenience we label starting from the top and going clockwise as G1, G2, ..., G64, and the chairs are stationary. The giant circular dining table along with the lamps, however, can rotate. Each lamp has a switch, and flipping the switch when the lamp is on turns it off, and vice versa. The game is as follows

1) The game consist of turns. At each turn, you tell the butler a list of chairs at which you want to switch the lamps' state.

2) The butler will then has the option of arbitrarily rotating the entire table before he apply the switches at the list of chairs in point 1). Please note that the butler must rotate the table in such a way that each chair is directly across from a lamp (rotating so that a lamp ends up midway between two chairs isn't allowed).

3) You may take as many turns as you'd like. If you succeed in turning all the lights on, you win.

Example: Let's say that currently all lamps are off except for the ones at G1, G3, and G5. You tell the butler to switch the lamps at G1, G3, and G5. The butler then rotates the table counter-clockwise 2 spaces. Now, the lamps at seats G63, G1, and G3 are on. The butler then proceed to switch the lamps at G1, G3, and G5. The end result is that now the lamps at G63 and G5 are on.

Show that there's a strategy that is guaranteed to turn all the lamps on.

[Faizaan]

For clarification, the Butler may turn the table in any direction and as may spaces as he wants, right?

[bushindo]

For clarification, the Butler may turn the table in any direction and as may spaces as he wants, right?

That is correct. The Butler may turn the table in any direction and for as many spaces as he wants.

[araver]

First thought: "Fire the butler. This is unfair. Plus playing games is probably not in his job description."

Then again.

If an honest man is presented with the game, the first reaction will undoubtedly be: "That's completely unfair. Whatever I hope to achieve by moving, he can counter-move and make a fool of me."

Now, an honest man presented with the same game, but this time one that has played chess (or any other game that involves playing with an adaptable adversary), confronted with the same game, will turn the tables (pardon the pun) and start with "The endgame. How can I move him into a position that allows me to finish this regardless of his tricky rotations? So ... 1) What is the confort zone for me in this game? and 2) How can I push him there?"

Part one first: 1) Game ends when all lights are on. If all lights are off, then I can instruct him to flip all, rendering his rotation pointless. So, all on OR all off are my initial confort zone.

What would also be in my confort zone? Clearly any situation where regardless of his rotation, the butler leaves me on familiar ground. Good. So, recursively, the confort zone can be defined as any instance in which there exists a move for me, which regardless of the rotation the butler chooses, lands inside the confort zone as well.

Wait, there's a loophole there in that definition. He can't expect to win this (unless I give up, grow old or the guests arrive), but how about stalling me forever. Yeah, that's a pitfall. So, if a rotation can bring me in position visited earlier, if loops can be formed, I've lost time. And that's not good for me. That's only good for the omnipatient (presumably immortal) butler.

Also, assuming the butler knows his game, and he doesn't want me to win (and that imaginary grin on the butler's face tells me he has no desire to let me win), then he will act to push me back to an earlier position. You know what they say: generation of random numbers is a far too important subject to be left to chance.

So, the confort zone has to be defined as any instance in which there exists a move for me, which regardless of the rotation the butler chooses, lands inside the confort zone in a different position. There might still be closed sets of instances where one can move in circles.

Lets forget some lamps for a moment. Say there are only 2 chairs and lamps. The confort zone found so far tells me, that if all lamps are on or all off, I win (in 0 or 1 moves). So, what else is there? One is on and one is off. Again, I win, choosing a single lamp to turn on. Regardless of his rotation, after he turns a lamp on we are back to one of the situations where all lamps are synchronized (either all on or all off). For n=2, I win in at most 2 moves.

Looking back at the long table for 64 guests, one can only sigh and curse himself for inviting so many guests in the first place. Still, what I have so far: All in synch is good still for the long 64-people table as well. But if only 1 is on, the same move fails, the butler can simply rotate it somewhere else and I'll get stuck with 2 lamps on, somewhere around the table. So, 1 lamp on is no longer in the end-game.

What's the natural extension then? The natural extension would be an instance where all even lamps are on (or all odd ones). If I instruct him to light Gx with x even, then regardless of the rotation, we'd end up in a synchronized ALL-ON/ALL-OFF position. Any other position that seem rotation invariant?

None that obvious staring back at me, so let's go back to a smaller table.

Say, 4 guests, denote 1=light on, 0=light off. Confort zone: 0000, 1111. Oh, and 0101 and 1010 as seen above. 2^4-4 = 12 instances remaining. A lot are similar, so they should be met with similar moves. Any two instances which can be obtained from one another via rotation can surely be solved with the exact next move (if one exists). Same goes for an instance which is a negative image /reverse of another (since a 1111 move will reverse all of the lights).

So, out of the rest of the 12 instances, ignoring rotations, we get 1000, 1100 as the most important cases, all the others are similar via rotation or reversing. How do I deal with those? Well, first off, let's try throwing them back at them.

Case 1: See 1000 (or anything similar via rotation/reverse), play 1000, 4 possible moves for the butler yielding 4 possible instances: 0000, 1100, 1010, 1001. Two of them are already confort zone, the other two are the same via rotation, so let's jump to that other case (and make a mental note not to loop back). Also, the fact that none of the outcomes loops back to the same type of instances (including rotations) makes this a promising move.

Case 2: See 1100 (or anything similar via rotation/reverse), play 1100, 4 possible moves for the butler yielding 4 possible instances: 0000, 1010, 1111, 0101. Which is great since all the outcomes don't loop back and all move to the confort zone.

So, game over for n=4. I win in at most 4 moves. Longest game: Instances after the Butlermoves / Instructions from the Player: B1000-P1000-B1100-P1100-B1010-P1010-B0000-P1111-B1111-Game over-Player Wins (as he should, cause no one really wants the computer to win, right?)

Now, after this burst of success-related adrenaline cools off, what have I learned from this. I can win against kindergarden butlers using 4 lamps. Oh, did I mention I'm not quite sure how I'm winning? (even though I have a pretty decent idea of why I'm winning).

So, at this point someone with a background in Mathematics would look back at the problem, and facepalm after reading "Show that there's a strategy ..." Show, as in boringly prove to the butler there's no way to win. Not actually construct/play it.

Hmm. There should be some room left to wiggle there though.

First of all, we can't actually bore the butler with an elaborate proof using group theory, can we? No, sir. The easiest way that works with butlers is the good-old fashioned: "Put your money on the floor, flip them as you want and let's go for a spin, shall we?" (Not putting money on the table since we're, or at least he's moving that around too much for comfort).

So, not actually seeing a butler around at the moment, the next best thing is to list a strategy that's guaranteed to win and prove it to anyone who actually gets around to seeing a butler. And tries to/or is challenged by said butler.

Back to the drawing board, why exactly are winning for n=4? Well, that's easy to explain in 4 steps:

Step 0: If all are on (1111), you win.

Step 1: From all positions with no light on (0000), flip them all to win

Step 2: From all positions with alternate lights on (0101, 1010), flip them alternatively (1010) to go to step 1 or win.

Step 3: From all positions with two non-alternating lights on (1100, 0110, 0011, 1001), flip the first two (1100) to go to a step above (1 or 2).

Step 4: From all positions with one light on or three lights on (1000, 0100, 0010, 0001, 1110, 1101, 1011, 0111), flip the first only (1000) to go to a step above (1, 2 or 3).

Yeah, numbering from step 0 kinda feels like cheating, since I said there are only 4 steps. *shrug*

Now, you might ask "So, for n=64 that would be 64 steps or what?" Actually, no idea, since I'm typing as I go. But make sure to ask me around later. Though I can definitely tell you it's an even number of steps worst-case. With or without a step 0.

Let's get to the second part "2) How can I push the butler towards my confort zone?".

Well, we could try it with n=8 first, but let's maintain the analysis at n=4 for a while. How did we push him there?

- The number of lights on is not enough for n=4 to reach a conclusion (though it was enough for n=2) as evidenced by steps 2 and 3.

- Alternating instances are clearly the only ones "near" (always at most 1 step away, no matter what the butler chooses) from the initial confort zone (steps 0 and 1 above).

- There is something that differentiates between 1000 and 1100. Against intuition (read editing distance), 1000 looks farther from 1010 than 1100 is. Intuitively, symmetry plays a much bigger underlying role, yet to be discovered.

- When I said "throw back at" i.e. move like the instance looks like after rotations/reversing, I intuitively chose the simplest to represent move (e.g. 1000 instead of 0111 that works the same). But paying closer attention, any rotated and or reversed move would have worked. For example: instance 1000, moving 0111 (instead of 1000) leads to gives 1111, 0011, 0101 and 0110 as possible outcomes, same steps above, but one of which is even skipping step 1 entirely. Either way, (except for 0000), moving (adaptively) to mirror the exact instance one is in works in pushing the butler to a corner (the initial confort zone - steps 0&1).

So while a very simple strategy seems clear: "Except for the case when all lights are off, keep trying to mirror the lights that are on - as if you're trying to put all the lamps out if the butler does not rotate the table. Eventually, you'll win.", how can we:

- (mathematically) represent this distance and show it is strictly decreasing?

- and of lesser importance, what does "eventually" mean as a maximum number of steps (is it at most N for N lights, where N is a power of two)?

- and of even lesser importance right now, but probably an interesting afterthought, does it have to be an adaptive strategy, or can one do it blindly, even without seeing the initial position? (assuming something beeps when all lights are on).

Seeing that the table instances and the moves can be seen as n bits (or binary words of length n), it makes sense to try to formalize the operations involved in the game:

- Whenever one tries to flip all the lights, a binary XOR happens.

- However, the butler can rotate/shift the bits (but not scramble them entirely, that game would actually be unfair for n > 2).

So, the game is a succession of XORs. The first word is known (the initial position), the other words (moves) are only known up to a shift. But the complication comes from the fact that the adaptive strategy of "throwing back at it" means duplicating the whole operation at each step and shifting it (which actually leads to a tree with a lot of redundancies in it).

This approach does not look promising. Proving that the strategy works globally looks far harder than focusing on each step. One need not see from the first glance that a strategy will get them uphill. Instead, one could much easier be convinced that the strategy involves only moves that go uphill from a stair to one above. No stepping back, no stalling. The problem lies in drawing the stair right. Two options lie ahead:

A) if one draws it going down from the hilltop (11...111), the catch is in showing the stair captures (exhaustively) all the cases.

B) if one draws it going up, from an arbitary stair, the catch is in defining and computing the height of the stairs.

A probably works for N=64, by exhausting all possible cases. But B's where I put my money on.

End of spoiler. Warned you there was no proof here. Yet.

[plainglazed]

take the xor of the current position (with 1 and 0 representing on or off) and 101010101...0, rinse, repeat

[superprismatic]

The list you give the butler each time is a list of guests who are

at the lit lamps. Eventually, either they will all be lit or they

will all be out. If they're all out, give the butler a list of all

the guests.

Dealing with a hurricane at the moment - no time for more.

[plainglazed]

but definately still a guess without proof. take the xor of the current position of lamps on (1s) and lamps off (0s) and 1010101...0 and that is the direction you give the butler. repeat until you get all lamps around the table on or off. if all end up off, make one last selection of switching all the lights.

[bushindo]

Araver and superprimastic got the correct strategy ( nice analysis and intuition, araver). I'm interested in seeing more of superprimastic's input after the hurricane (be safe). As for me, I was able to prove that the strategy is guaranteed to win using

we let the list of lamps states be a 64-dimensional binary vector. There exist a matrix operator that corresponds to the strategy described by araver and superprimastic. Turns out that this operator has certain special properties, and applying it after a certain number of time will take the original vector to 0.

[bushindo]

but definately still a guess without proof. take the xor of the current position of lamps on (1s) and lamps off (0s) and 1010101...0 and that is the direction you give the butler. repeat until you get all lamps around the table on or off. if all end up off, make one last selection of switching all the lights.

Using the proof technique that I posted in post #8, I was able to verify that this strategy would also guarantee that we would win in the end. Good work!

[plainglazed]

...having only two lamps initially on, either adjacent or seperated by 1,3,7,15 or 31 lamps off allow the butler a continuous loop with the strategy of having the butler's switch positions being the lights that are currently on?

1100000000000000000000000000000000000000000000000000000000000000

1010000000000000000000000000000000000000000000000000000000000000

1000100000000000000000000000000000000000000000000000000000000000

1000000010000000000000000000000000000000000000000000000000000000

1000000000000000100000000000000000000000000000000000000000000000

1000000000000000000000000000000010000000000000000000000000000000

100000000000000000000000000000000000000000000000000000000000000100

EDIT: see spoiler . almost put a pot of coffee on before posting this.

[bushindo]

Adding additional hints for proving that the optimal strategy described by araver and superprimastic will guarantee a win

Let y be a binary 64-dimensional vector where 1's correspond to a lamp being on, and 0's correspond to a lamp being off. Let I be a 64x64 identity matrix, and let A be a rotation matrix that rotates the entire vector by 1 space. We can construct A by starting with an identity matrix and then 'lifting' the diagonal up 1 row. For instance, a small example of A that is 8x8 would be the following matrix

	[,1]	[,2]	[,3]	[,4]	[,5]	[,6]    [,7]    [,8]

[1,]	0	1	0	0	0	0	0	0

[2,]	0	0	1	0	0	0	0	0

[3,]	0	0	0	1	0	0	0	0

[4,]	0	0	0	0	1	0	0	0

[5,]	0	0	0	0	0	1	0	0

[6,]	0	0	0	0	0	0	1	0

[7,]	0	0	0	0	0	0	0	1

[8,]	1	0	0	0	0	0	0	0

So, if we are given a vector (a, b, c, d, e, f, g, h), then

A * (a, b, c, d, e, f, g, h)' = (b, c, d, e, f, g, h, a)'

A² * (a, b, c, d, e, f, g, h)' = (c, d, e, f, g, h, a, b)'

So, let's go back to the case where y is a 64-dimensional vector. We define A as a 64x64 rotation matrix. It is easy to see that a turn of the game where we apply the strategy described by araver and superprimastic correspond to the matrix

(I - Aⁿ)

where n is the number of spaces that the butler choose to turn the table clockwise before applying the switches. So, for instance, if we play 3 turns using the winning strategy, and the butler turned the table 5, 19, and 3 spaces, respectively, then the current state, y_c, corresponds to the followings

y_c = (I - A³) (I - A¹⁹) (I - A⁵) y

where all the calculations are done modulo 2.

[bushindo]

Adding more hints for completing the proof. See post above for background.

The product of the operator (I - Aⁿ) is communicative. That is, (I - Aⁿ) (I - A^m) = (I - A^m) (I - Aⁿ).

Because A rotates the vector y by 1 space, then after 64 rotations, we are back to the original y. So,

I = A⁶⁴,

I - A⁶⁴ = 0,

[Guest]

great puppze.

Adding additional hints for proving that the optimal strategy described by araver and superprimastic will guarantee a win

Let y be a binary 64-dimensional vector where 1's correspond to a lamp being on, and 0's correspond to a lamp being off. Let I be a 64x64 identity matrix, and let A be a rotation matrix that rotates the entire vector by 1 space. We can construct A by starting with an identity matrix and then 'lifting' the diagonal up 1 row. For instance, a small example of A that is 8x8 would be the following matrix

	[,1]	[,2]	[,3]	[,4]	[,5]	[,6]    [,7]    [,8]

[1,]	0	1	0	0	0	0	0	0

[2,]	0	0	1	0	0	0	0	0

[3,]	0	0	0	1	0	0	0	0

[4,]	0	0	0	0	1	0	0	0

[5,]	0	0	0	0	0	1	0	0

[6,]	0	0	0	0	0	0	1	0

[7,]	0	0	0	0	0	0	0	1

[8,]	1	0	0	0	0	0	0	0

So, if we are given a vector (a, b, c, d, e, f, g, h), then

A * (a, b, c, d, e, f, g, h)' = (b, c, d, e, f, g, h, a)'

A² * (a, b, c, d, e, f, g, h)' = (c, d, e, f, g, h, a, b)'

So, let's go back to the case where y is a 64-dimensional vector. We define A as a 64x64 rotation matrix. It is easy to see that a turn of the game where we apply the strategy described by araver and superprimastic correspond to the matrix

(I - Aⁿ)

where n is the number of spaces that the butler choose to turn the table clockwise before applying the switches. So, for instance, if we play 3 turns using the winning strategy, and the butler turned the table 5, 19, and 3 spaces, respectively, then the current state, y_c, corresponds to the followings

y_c = (I - A³) (I - A¹⁹) (I - A⁵) y

where all the calculations are done modulo 2.

very good puzzle.

if the initial is y, after shift it is A^n y, and after light up

it become y XOR A^n y

it is no y - A^n y.

[bushindo]

great puppze.

very good puzzle.

if the initial is y, after shift it is A^n y, and after light up

it become y XOR A^n y

it is no y - A^n y.

I'm afraid I don't follow this post. With the last sentence, did you mean to say,

it is now y - A^n y,

or

it is not y - A^n y ?

[Guest]

I'm afraid I don't follow this post. With the last sentence, did you mean to say,

it is now y - A^n y,

or

it is not y - A^n y ?

sorry it is not y - A^n y

[bushindo]

sorry it is not y - A^n y

In binary modular arithmetic, y XOR Aⁿ y is indeed equivalent to (y - Aⁿ y), as the following table will show

Notice that for a and b in the discrete set (0, 1), (a XOR b) is indeed equal to (a + b) mod 2.

[bushindo]

Adding the proof to complete the puzzle. Please excuse the formatting; typing a proof in the brainden editor is quite complicated.

See post and for background.

Lemma = Given that (1- A^64m ) = 0 (see hint 2 in post #12) , then (1- A^m )⁶⁴ = 0 for m in the discrete set (0, 1, ..., 63 ).

Proof: (I- A^m )⁶⁴ = [ (I - A^m)² ]³²

= [ I - 2 A

m

- A

2m

]

32

#comment#

2 A

m =

0 and A = -A since we are working with binary modular arithmetic

= [ I - A

2m

]

32

Repeat the process 5 more times, and we get (1- A

m

)

64

= 0.

Claim

: The optimal strategy for the game in the OP will eventually win in at most [ 64 (64-1) + 1 ] turns.

Proof

: The optimal strategy, when applied to a game with r turns, corresponds to the following matrix operations (see post #11 for background)

y

c

= ( I - A

ar

).........( I - A

a2

)( I - A

a1

) y , where ai is the rotation amount that the butler does at turn i.

After [64(64-1) + 1] turns, by the pigeon hole principle, some rotation by m spaces must have been used 64 times. Since our matrix operator is communicative (see hint 1 of post

), then

y

c

= ( I - A

m

)

64

......... y

y

c

= 0 * ............. y by the lemma.

[plasmid]

I think that I'm missing something in the solution. It seems to prove that (I-A^m)⁶⁴ = 0. That's fine and good, but doesn't that just mean that if the butler chooses some number m and always rotates the table by m seats, then the strategy will work? I thought that the butler could choose a different random number of seats to turn the table on each move (otherwise it would be pretty easy to solve it in two turns).

[superprismatic]

I think that I'm missing something in the solution. It seems to prove that (I-A^m)⁶⁴ = 0. That's fine and good, but doesn't that just mean that if the butler chooses some number m and always rotates the table by m seats, then the strategy will work? I thought that the butler could choose a different random number of seats to turn the table on each move (otherwise it would be pretty easy to solve it in two turns).

Well, Bushindo is saying that, taking enough steps, there must be a rotation which is used at least 64 times (since there are a finite number of them -- 64 to be exact). Whichever rotation that is, call it m, (I-A^m)⁶⁴ = 0.

[plasmid]

Oh, that's right. "Lemma" means lemma, "claim" means what we're trying to prove.