## January 2014 riddle

UPDATE (6 January): Clarification: Answer either of the riddle's two parts for credit. The idea is that people with no prior familiarity with Part 1 can get credit by solving only it, whereas people with prior familiarity with Part 1 can get credit by solving Part 2.

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:

The genie's actions, as described above, permute the cups by taking each cup that was at position x and switching it to position (x+k) mod n, where the genie chooses a new k after every check.

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

k : 0≤k<n},

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.
We assume, in all cases, that the identity permutation (leaving all cups in their original positions) is part of the genie's repertoire. Also, for the purposes of Part 2, assume that n is such that there exists a winning strategy against the genie according to the rules of Part 1.

### List of solvers:

#### Part 1:

Guangda Huzhang (6 January 20:22)
T.T. Msh (16 January 22:22)
Harald Bögeholz (17 January 08:36)

#### Part 2:

T.T. Msh (17 January 17:17)

Elegant and original solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!