First, let us prove that when n is not a power of two, the genie can continue the game indefinitely. Let n=2m(2k+1). We describe an easier game (in the sense that to win it you have more than just the option of getting all the cups to be right-side-up). Let a cup that is right-side-up be designated as a "0" and one that is upside-down be designated as a "1". We take the exclusive OR (XOR) of all the bits associated with cups that are in the same position modulo 2m. This leads to 2k+1 bits. The "easier" game is won not only when the cups are all right-side-up, but whenever the resulting 2k+1 bits are all equal.
The claim is that regardless of what non-winning list of 2k+1 bits we take as the "current" state, there is no choice of cups to turn over that will guarantee a win regardless of what the genie does. Let us verify this claim. If we take any cup that the player chooses to turn over to be a "1" and any cup that the player chooses not to turn over to be a "0", and then narrow the list from n bits to 2k+1 bits using the same procedure as before, then the new 2k+1 bits, chosen by the player, get XORed to the existing state after some unknown cyclic shift to create the new state.
If for some cyclic shift (say, shift by zero) this leads to a winning configuration, this means that the state was either exactly the vector chosen by the player or its bitwise negation. So, if the original state was X, the player's choice must have been either P=X or P=not(X) to win. If so, then the genie's strategy is to cyclically shift X by 1. Because X's bits are known not to all be equal (or else it would have been a winning configuration), X cyclically shifted by one does not equal to X. For P to be a winning move against this new configuration as well, the new configuration must therefore equal not(X). However, because the number of bits in X is odd, its number of zero bits cannot equal its number of one bits, so X's negation cannot equal X cyclically shifted by 1.
For n values that are powers of 2, we win using the following strategy:
If all bits are zero, this indicates that the cup orientations are some vector X repeated twice: XX. If the player now turns the cups over in some pattern YY this will maintain this invariant. Furthermore, the resulting ZZ will have the same possible Z values as in a game with n/2 cups, where the initial position was X and the player's move was Y. We can therefore simply use the original strategy for n/2, doubling the vectors as we go. Because the original strategy guaranteed that we reach 0 at some point, now we are guaranteed to reach 00 and win.
What, then, do we do if the n/2 bits (the result of XORing) is not the zero vector, when we begin? Then we simply use the original strategy for n/2 in order to zero it. (This time, if the original strategy called for Y, our move will be 0Y.) We test whether we succeeded (the n-length pattern is an XX-type doubling) by running the procedure described above that wins and stops the game if the initial pattern was a doubling. (Note that by turning the cups over in a doubled-pattern we never change the result of the n/2-length XORing.)
In total, if the n/2-cup solution required k checks, the new solution requires k2. By induction, the full procedure takes 2n.
To see that this is best possible, suppose that one has a strategy that requires k<2n checks. The genie has, in this scenario, some table-turning strategy that guarantees the game will last k checks. The last of these checks will end up with the zero vector (because, by assumption, we've won), but the others will have some other vector values. Because k<2n, there will still be some value of the vector, Y, that did not appear in any check. Let us XOR the original state of the cups by this value, but not change any other part of the genie's strategy.
In the new game, the cup tests will now yield whatever they originally yielded XOR Y. This means that none of them, not even the last test, will be zero. So, the genie can force the game into round k+1 -- a contradiction.
Q.E.D.
Final remarks:
What the genie riddle gives us is another such basis:
00000001, 00000011, 00000101, 00001111, 00010001, 00110011, 01010101, 11111111, etc.,
that has similar "counting" properties, but has the added benefit that these counting properties do not get ruined by cyclic shifts. In more standard math terminology: these vectors remain linearly independent even after each is shifted cyclically by an arbitrary amount (chosen separately for each).
Another way to describe these is as Sierpinski's triangle (Pascal's triangle modulo 2).
The last 22^k moves in our original strategy, for any k, are vectors that contain only repetitions of bit-patterns of length 2k. This means that the state of the cups at the beginning of this sequence of moves is exactly the set of vectors that are, themselves, repetitions of bit-patterns of length 2k. (Anything other than this would not turn to zeroes if the genie opts to simply leave the cups as they are, and if some of these cannot appear in the input to the last 22^k moves then the remaining moves must handle more options than there are checks, something that was shown to be impossible in the optimality argument of Part 1.)
It also means that none of the genie's possible permutations can disrupt this invariant (or else, again, no combination of the actions used in the last 22^k steps can fix the invariant, if the genie chooses from this point on to do nothing).
This indicates that the possible permutations by the genie must be some subset of the permutations maintaining this invariant. These are the permutations that first divide the original vector into segments of length 2k and applies some arbitrary permutation (the same permutation) on each segment, and then permutes by arbitrarily chosen permutations (which may be distinct) the cups that are in positions that are equivalent modulo 2k.
The intersection of all these constraints is the set of permutations sought. To describe it explicitly, we can unravel it starting with k=0 and going up. The final description is that each permutation is defined by a set of functions, {fk | 0≤k<m}, where each fk is a function that takes k bits and returns a single bit, such that if the permutation is y=π(x) then, for each k, yk equals xk XOR fk(xk-1,..., x0).
Clearly, each of these is distinct, because the identity of each fk can be determined uniquely by observing π. Their total number can be computed by the number of such functions. One needs 2k bits in order to describe fk, so describing all functions together requires 2m-1=n-1 bits. In total, this is a set of size 2n-1.
For the original strategy to work, we need to show two properties that were required in the original proof for n>1, both of which are clearly satisfied from the definition of π.
Q.E.D.
I am leaving it to the readers to show how all of the genie's original cyclic permutations can be described as instances of this larger class. The new set includes also other interesting permutations, such as mirroring, which the reader may also wish to find. Another interesting property of this set is that it is closed to permutation combinations, and readers may want to ascertain this fact, too.