Ponder This Challenge - July 2004 - N cups on a turntable

Ponder This Challenge:

Puzzle for July 2004.

This month's puzzle comes from Aditya K Prasad, who heard it from a friend. It is similar to our November 2002 puzzle (from Martin Gardner's February 1979 Scientific American column), but with an important difference. To be considered for publication, please supply answers for BOTH parts of the puzzle.

Part 1:
There is a round table divided into 4 equal quadrants, with one cup in each quadrant. The quadrants are labeled with letters (A, B, C, D) that do not move. Initially, each cup is randomly face-up or face-down. You are blindfolded and put in front of the table. On each turn of the game, you instruct a genie to flip the cups in whichever positions you choose (e.g., you may say "flip the cups in A and B"), possibly choosing no cups or possibly all four. The genie complies. At this point, if all the cups on the table are face-up, the genie will tell you that you have won the game and are free to go. If not, he rotates the cups randomly (possibly not rotating them) and you play another turn. Give a strategy to win this game in a finite number of moves (the solution is not unique).

Remark: the outcome of "rotation" the four cups is one of the four possible positions: the cups originally at (A,B,C,D) can be at (A,B,C,D), (B,C,D,A), (C,D,A,B), or (D,A,B,C). It is not an arbitrary permutation.

Notice that you cannot examine the current orientation of any cup at any time. This contrasts with the earlier puzzle.

Part 2:
Suppose that instead of 4, there are n divisions and cups. For which n is it possible to guarantee a win? Prove your answer is correct.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  ANSWER:

  The solution is possible exactly when n is a power of 2.

  Suppose n is not a power of 2, so n=r*2^s with r odd and r at least 3. Label the cups 0 through n-1. Also, "face-up" and "face-down" will be called values "0" and "1", respectively. Let the two "special" cups 0 and 2^s start out with opposite
  orientations. In the requested move, consider the positions with labels (i*2^s, i=0,1,...,r-1). Since r is odd, the requests (move, non-move) among these r positions cannot strictly alternate: there are two requests, separated by exactly 2^s, which agree (either both are to move, or both are not to move). Imagine that the cups have been rotated before fulfilling this request, so that our two special cups (initially at 0 and 2^s) fall into these two positions. Then after the move, these two cups still have opposite orientations. This can go on forever, no matter what we request.

  Suppose instead that n is a power of 2. We will use induction to create a sequence of (2^n)-1 requests which will satisfy the problem. If n=1, one move suffices: (0). (That is, we have a single request, which is to flip the single cup at position 0.) Either the cup is face up before the move, or it is afterwards. Now suppose n=2m, where m is a power of 2. Let S=(s_1,s_2,...,s_((2^m)-1)) be a sequence which works for m, where each s_i is a subset of {0,1,...,m-1}. Construct a sequence T=(t_1,t_2,...,t_((2^n)-1)) with t_i in {0,1,...,n-1}. The move t_(i*2^m) is s_i (it only operates on the first m elements); it is called an "outer move". The move t_(i*2^m+j), j=1,2,...,(2^m)-1, is (s_j,m+s_j). That is, operates on first m elements the same way s_j did, and also acts identically on the second m elements. These "inner moves" (t_(i*2^m+j), j nonzero) leave the relation between items x and m+x the same: either they remain identical or they remain opposite each other. Only the "outer moves" (t_(i*2^m)) change these relations. Keeping track of the relations, r_i=(x_i + x_(m_i)) mod 2, i=0,1,...,m-1, there are only m of them; one of the (2^m)-1 outer moves (say t_(i*2^m)) brings all these relations to all 0, by induction. Then during the block of inner moves between i*2^m and (i+1)*2^m, we have always x_k=x_(m+k), and the inner moves bring all the x_k (k<m) to 0, simultaneously bringing the x_(m+k) also to 0.

  For n=2, the complete set of 3 moves is (0,1), (0), (0,1).

  For n=4, the complete set of 15 moves is
  (0,1,2,3), (0,2), (0,1,2,3), (0,1),
  (0,1,2,3), (0,2), (0,1,2,3), (0),
  (0,1,2,3), (0,2), (0,1,2,3), (0,1),
  (0,1,2,3), (0,2), (0,1,2,3).

  For n=8 there are 255 moves.

  The number of moves, (2^n)-1, is clearly optimal: we get exactly 2^n chances to win (counting the initial position), and if the cups were initially random, each time we would have a chance 1/2^n of winning.

  "Tomas Rokicki points out that the solution actually requires 2^n moves, rather than 2^n-1, because the genie does not tell us whether our initial configuration is already a winner."

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

• Luke Pebody (7.06.2004 @01:16:42 PM EDT)
• Joe BGI SF Fendel (7.07.2004 @12:12:23 PM EDT)
• Jonathan Derryberry (7.07.2004 @01:24:17 PM EDT)
• Hagen von Eitzen (7.08.2004 @04:01:52 AM EDT)
• Evgeniy Tarassov (7.08.2004 @09:51:41 AM EDT)
• A.F.Jarvis (7.08.2004 @11:11:10 AM EDT)
• Nilesh Dalvi (7.09.2004 @02:26:17 AM EDT)
• James Dow Allen (7.09.2004 @04:10:55 AM EDT)
• Bill Roscoe (7.09.2004 @08:39:17 AM EDT)
• Atif Hussain (7.09.2004 @10:44:17 AM EDT)
• Patrick J. LoPresti (7.09.2004 @12:26:25 PM EDT)
• Shiva P Kasiviswanthan (7.09.2004 @02:45:44 PM EDT)
• Mark J. Tilford (7.11.2004 @03:46:14 PM EDT)
• Michael Brand (7.12.2004 @04:45:38 AM EDT)
• David McQuillan (7.12.2004 @01:48:09 PM EDT)
• John G. Fletcher (7.13.2004 @09:34:06 PM EDT)
• Daniel Bitin (7.14.2004 @04:26:42 AM EDT)
• Rocke Verser (7.14.2004 @06:56:29 AM EDT)
• Mark Sandler (7.14.2004 @04:48:21 PM EDT)
• Clive Tong (7.15.2004 @03:57:34 PM EDT)
• David Woodruff (7.16.2004 @06:29:37 AM EDT)
• Jian Li (7.17.2004 @11:32:20 AM EDT)
• Bart De Vylder (7.19.2004 @08:49:02 AM EDT)
• Peter Huggins (7.20.2004 @02:31:19 PM EDT)
• Colin Bell (7.20.2004 @04:55:55 PM EDT)
• Derek Kisman (7.21.2004 @04:52:27 AM EDT)
• Agricul Turemistake (7.22.2004 @01:00:34 AM EDT)
• Alex and Igor Naverniouk (7.22.2004 @03:21:34 AM EDT)
• Tomas G. Rokicki (7.22.2004 @04:38:35 AM EDT)
• Hao Wu (7.23.2004 @11:55:02 AM EDT)
• Wolfgang Kais (7.25.2004 @10:36:48 AM EDT)
• D (7.25.2004 @10:56:32 AM EDT)
• harma Deep (7.25.2004 @10:56:32 AM EDT)
• Mayank M Kabra (7.27.2004 @12:14:37 AM EDT)
• Yoo Je-Sung (7.27.2004 @07:27:28 AM EDT)
• Amit Sinha (7.28.2004 @03:53:00 PM EDT)
• Dan Dima (7.29.2004 @09:19:36 AM EDT)
• Behdad and Behnam Esfahbod (7.29.2004 @07:37:24 PM EDT)
• Coserea Gheorghe (7.31.2004 @11:16:35 AM EDT)