Home > Just Math
| N cups on a turntable (Posted on 2019-01-13) |
 |
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.
approach
|
Comment 1 of 1
|
We begin with no move, just in case the four cups are faced up. Inmediately after, we ask to flip the 4 cups, just for the possibility that the four cups are faced-down.
My approach would be to expose an algorythm based on pairs.
If the inicial ignored state is with two cups faced-up and two face-down the action of flipping any pair of cups only have three outcomes: 4 cups up (the game is finished), 4 cups down and then next move to perform is 4 cups flipped (and the game is finished), or two cups faced-up and the other two faced down.
In this last case we change the selection of the cups. If the inicial selection picked the cups of positions A & B, and we didn't succeed, the next selection consider cups on positions A & C. We are going to pick one or two different cups, because even if the table can rotate, the cups on random positions A & C are always separate by B. The cups faced-up or are side-by-side or are separate with another cup.
Anyway there is a caveat. For A & C te work and finish the game we need that the cups in positions A & C have the same parity. But we perform A & B before A & C. When we perform A & B followed by flip 4, both cups placed on A & B take the same position that they had before. Instead the cups on C & D change their value. If, for example, they were faced up and down they finish down and up. Then it could happen that if the cups on A & C were same faced, performing A & B and flip 4 change the cups on A & C to opposite values. But then flipping A & C is not going to work. To avoid that and to be sure that when we apply A & C they have cups with same parity we can perform A & B and A & C in sequence two times. If the first time do not work, the second will do it.
During this process or, at least, in the end of it, we should have all the cups faced down (and we ask to flip all 4) or all up (game finish).
If, instead, we don't get anything here, it means that the initial position was with 1 or 3 cups faced-up. Then we flips A & B & C (or we flip just A, it's same to our goal). We will get 0, 2, 4 cups faced up. So we are in the precedent situation, and go ahead with the algorythm.
===== Sommary
No move Flip 4 Flip A & B Flip 4 Flip A & C Flip 4 Flip A & B Flip 4 Flip A & C Flip 4 Flip A & B & C Flip 4 Flip A & B Flip 4 Flip A & C Flip 4 Flip A & B Flip 4 Flip A & C Flip 4 Exit
Edited on January 13, 2019, 7:27 pm Edited on January 14, 2019, 2:07 am
|
|
Posted by armando
on 2019-01-13 11:46:32 |
|
|
Please log in:
Forums (1)
Newest Problems
Random Problem
FAQ |
About This Site
Site Statistics
New Comments (14)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox:
|
