Author |
Topic: The Blind Bartender (Read 3139 times) |
|
Jonathan_the_Red
Junior Member
Gender: 
Posts: 102
|
 |
The Blind Bartender
« on: Aug 5th, 2002, 12:03pm » |
 Quote  Modify
|
Apologies if this has already been posted elsewhere... if so, I didn't see it.
You are blindfolded and seated at a small square table which has a shotglass at each corner, some of which may be facing up, others facing down. The table may be rotated to any orthogonal position. Your goal is to orient all four shotglasses the same way, either all up or all down.
At each "turn", the table will be rotated to a new position (or possibly the same one.) You may then reach out with your two hands and select two shotglasses. You will be able to tell the orientation of those two glasses. You may reorient those two however you'd like. Once you're satisfied, the table will be rotated again, and the process repeats. The game ends when you've won.
What strategy can you use to ensure victory?
Secondary problem (much harder): if the table has N sides, and the player has K hands, what's the minimum K in terms of N for the game to be solvable? In this special case, N=4 and K=2.
|
| « Last Edit: Oct 23rd, 2003, 7:54pm by Icarus » |
 IP Logged |
My arcade cabinet
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: NEW PROBLEM: The Blind Bartender
« Reply #1 on: Aug 5th, 2002, 12:11pm » |
Quote Modify
|
This is very much like the "Button Trap Room" problem under "Hard", except that in that problem you cannot tell the orientation of the buttons (shot glasses), and can only toggle them.
The generalization here sounds interesting.
|
|
IP Logged |
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: NEW PROBLEM: The Blind Bartender
« Reply #2 on: Aug 15th, 2002, 2:28pm » |
Quote Modify
|
Are we required to win in a bounded number of steps? If you always pick two glasses at random and turn them both face up, then you're guaranteed to win eventually, but you don't know how long it'll take.
Otherwise:
1: Take both cups on one edge, and turn them both face-up. If we don't win, we know that one or both of the others is still face-down.
(spin)
2: Take two cups on one edge. If they're both face-down, then we can win immediately by turning them both face-up.
If they're both face-up, then turn them both face-down. Either this will win, or we know that the other two are one of each: If the other two were both up, we would have won last round, and if they're both down, we win this round. Either way, we know that we now have three down and one up.
(spin)
3: Take two cups across a diagonal from each other. If one is up, we know that that's the only "up" on the table, so we just turn it down and win. If they're both down, we flip one of them up at random. Now, we have
UU
DD
or some rotation of that.
(spin)
4: Take two cups on one edge, and flip them both. If they were both the same, then we just matched them to the other pair and won. If they were different, then we've created
UD
DU
or a rotation of that.
(spin)
5: Take two cups on a diagonal, and flip them both. We've just matched them to the other diagonal pair and won.
(you can actually skip step 2 if both cups are the same at the beginning of step one, but I couldn't think of a nice linear way to describe the plan then)
As for the most general problem, I think that you need at least N/2 hands (rounded up), but I'm not certain of that. And if you want to generalize it even more, we can replace the shot glasses (with two possible states) with something else with M different states.
//Hide tags added by Icarus to replace poorly-hidden-by-color answers (this post pre-dates the introduction of hide tags.)
|
| « Last Edit: Oct 23rd, 2003, 7:56pm by Icarus » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print