Using your Head is Permitted

UPDATE (2 January): A few readers expressed prior familiarity with this generalization of the classic genie riddle (I'll give references on the solution page), so I decided to add another question to it. See Part 2, below.

This month's riddle is a generalization, due to Oded Margalit (Thanks, Oded!), to a classic puzzle.

You've been trapped by a genie in a dark room, and your only hope of escaping is to solve the genie's puzzle. The genie places n cups equally-spaced along the perimeter of a circular table in front of you. You can feel the cups, but because the room is dark you cannot tell if the cups are right-side-up or upside-down.

The genie allows you to turn over any subset of the cups that you want (potentially turning them right-side-up, if their original orientation was upside-down), and, after doing so, to let go of the cups and ask the genie to check their orientation. If they are all right-side-up, the genie will let you go. If not, you can try again. The genie allows you to try as many times as you want.

The catch, however, is that as soon as you let go of the cups and ask the genie to check them, the genie swivels the table around, so the next time you touch the cups, they will have rotated an unknown number of degrees.

To make matters worse, the genie -- being a genie -- knows exactly what strategy you are planning, and will rotate the table in exactly the way that will prolong the game as much as possible.

This month, for credit, answer all of the following questions (in either or in both of the following two parts):

Part 1:

1. For which values of n will you ever be able to leave the room? For n values for which it is impossible to win against the genie, provide proof that this is the case.
2. For the n values for which it is possible to win, describe a strategy that will get you out of the room as fast as possible, and prove that it is optimal.

Part 2:

Another way to describe the same process is to say that the genie has, at its disposal, a set of permutations

defined by π_k(x)=(x+k) mod n, and the genie merely picks, after each check, one of these to apply.

The question: what is the richest set of permutations that the genie can use without this affecting the success of the strategy you discovered in Part 1? Please supply the following.

1. A description of the permutations in the set (in a way that does not describe the same permutation in multiple ways).
2. The total number of permutations in the set.
3. Proof that the original strategy will continue working, even when these new permutations are admitted to the genie's repertoire.
4. Proof that no larger set of permutations exists for which the original strategy will continue to hold.

List of solvers:

Part 1:

Part 2: