|
This one's not too hard, but pretty cool imo.
There is a room with a cross-shaped table in it. The cross-shaped table can spin around, but it always stops spinning with the arms of the cross facing north, south, east, and west. (i.e. after every spin, the cross will be in one of 4 possible orientations). At the end of each arm of the cross is a cup, either right-side up or upside down, at random.
Now you are in a separate room and cannot see the table, while your friend is in the room with the table. You can command your friend to flip over certain cups by telling him which directions to flip (i.e. if you say flip over the north cup, then your friend will flip the cup on the north arm from right-side up to upside down or vice versa). After your friend flips the cups, he will either say you're done because all the cups are right-side up, or he will spin the table. After he spins it, you can once again give him another command, and the process continues until all the cups are right-side up.
Your goal is to flip all the cups right-side up. Figure out a way to do this in as few spins as possible, and prove that it is optimal.
|
South Africa4316 Posts
Are the spins random (eg. it can spin 90 degrees or 270 degrees) or are the always exactly one spin to a side?
|
Nice problem. 
edit: I interpreted it as spins can be totally random {0, 90, 180, 270}. Also it seems worth pointing out more clearly that the OP says you can flip any number of cups in any of the directions, not just one cup each go.
+ Show Spoiler [Solution] +
I'll use the notation e.g. 0000 to mean all cups are upside down, and 1010 to mean that either North/South or East/West are right-side up; and the analogous notation to indicate which cups to flip. Let X be the initial configuration.
Here's one way with 16 worst-case flips. (Numbered from 0 due to not thinking of one case initially and not wanting to edit step numbers.)
0. Flip none of the cups. If X=1111 then done and your friend is a sneaky bastard.
1. Flip all 4 cups. If X=0000 then done. So now you've eliminated the possibility that all four of the cups had the same initial parity.
2. Now try to eliminate X=1010. This configuration wouldn't have been changed by flip 1. Flip 1010. X=1010 would now give you either 1111 (done) or 0000.
3. Flip all 4 cups. X=1010 is now eliminated.
4. Now try to eliminate X=1100. This configuration wouldn't have been changed by flips 1-3. Flip 1100. Now if X=1100, then the current possibilities are 1111, 1010, or 0000. So in steps 5-7, follow steps 1-3 by which we eliminated those possibilities previously.
5. Flip all 4 cups.
6. Flip 1010.
7. Flip all four cups. Now X=1100 is eliminated. Now all possibilities with X having an even number of 1's are eliminated.
8. Now the only possibilities left are X having an odd number of 1's. This property would be invariant under the flips 1-7. Flip 1000. Now the current configuration must have an even number of 1's.
9-15. Follow steps 1-7.
To prove that that's optimal, consider the simpler problem where there's no table spinning so the directions stay constant. This is a degenerate special case of the above in which every spin doesn't change anything, so solving this case is a necessary condition to being able to solve the general case. There are 2^4 = 16 possible initial configurations (each cup has 2 possibilities: up or down). For any given pattern choice of flips, you eliminate at most one initial configuration of cups per flip; so you need 16 flips.
|
yeah, Im either interpretting this wrong, or its totally random whether or not you get it . Im hoping its an interpretation error. Could you please explain the situation in a little bit more detail.
Do all cups start in a certain orientation?
Does the table spin randomly?
How many cup turns do we get per cycle?
|
the spins are random.
The cups' starting orientations are also random. They could all be right-side up, or only one is upside down, or however.
You tell you friend which cups you want to flip over by telling him which of the four directions to flip.
For example, if your table looks like this (1 means right side up, 0 means upside down):
1
0 0
0
The command "flip the north and south cup" gives you this:
0
0 0
1
This is the basic order of events.
1) Tell him which cups you want flipped over
2) Your friend flips the cups you designated
3) If they're all right-side up, your friend says you're done. Otherwise, he spins the table
4) The table randomly stops in a new random position
5) Go back to step 1
|
nvm, thought it through a bit more, your solution makes sense. 
|
|
|
|
|
|
EPT
