Here's one of my favorites:
Imagine that you've got a barrel sitting on a lazy-susan and it has four equally-spaced holes around its base. Inside each hole is a glass, and each glass is either right-side-up or upside-down. A move consists of reaching into any two holes, feeling the configuration of the two glasses inside, and leaving them as they were, or reversing one or both of them. You can't leave them lying on their sides or anything like that: this is a pure mathematical puzzle.
After each such move, however, the barrel is spun around so that you lose complete track of which holes were in which positions. Basically, you only have two options for holes: a pair of opposite holes or a pair of adjacent holes, and there's no way to tell which opposite or which adjacent holes you've chosen.
The goal is to have all four glasses the same: either all facing up or all facing down. There is an oracle that will instantly tell you if you have reached a "solved" configuration and the game stops at that point.
Can you provide an algorithm that will guarantee that the game ends in a fixed, finite number of moves?
Obviously, you could keep spinning, reaching in at random, and making sure all the glasses were up, but since you only get to investigate two holes at a time, the downward-facing glass could be missed for any number of spins, so that's not a good solution.
By reaching first into opposite and next into adjacent holes, you can guarantee that three of the glasses will all be up after just two moves, but finding the fourth glass could take arbitrarily long.
Imagine that you've got a barrel sitting on a lazy-susan and it has four equally-spaced holes around its base. Inside each hole is a glass, and each glass is either right-side-up or upside-down. A move consists of reaching into any two holes, feeling the configuration of the two glasses inside, and leaving them as they were, or reversing one or both of them. You can't leave them lying on their sides or anything like that: this is a pure mathematical puzzle.
After each such move, however, the barrel is spun around so that you lose complete track of which holes were in which positions. Basically, you only have two options for holes: a pair of opposite holes or a pair of adjacent holes, and there's no way to tell which opposite or which adjacent holes you've chosen.
The goal is to have all four glasses the same: either all facing up or all facing down. There is an oracle that will instantly tell you if you have reached a "solved" configuration and the game stops at that point.
Can you provide an algorithm that will guarantee that the game ends in a fixed, finite number of moves?
Obviously, you could keep spinning, reaching in at random, and making sure all the glasses were up, but since you only get to investigate two holes at a time, the downward-facing glass could be missed for any number of spins, so that's not a good solution.
By reaching first into opposite and next into adjacent holes, you can guarantee that three of the glasses will all be up after just two moves, but finding the fourth glass could take arbitrarily long.
posted by:
|
SF Bay Area
|
-
Re: Barrel puzzle
Thu, April 20, 2006 - 8:44 AMThanks for posting.
Okay, I have a method, but I think there may be a problem with it...not sure.
Scroll down
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1) turn any two adjacent glass up
2) turn any two opposite glasses down. At this point you know that you have two opposite Downs, one Up between them, and one Unknown.
3a) On this turn, reach for opposites again. If you find two Downs you know they're the ones you already turned and you leave them alone.
3b) If you find at least one Up, you know you don't have the ones you turned down. So turn them down.
4-infinity) keep reaching for opposites until 3b is satisfied.
Ok, so this works, except for the pesky "infinity" problem. I guess this solution doesn't provide a fixed number of steps. But am I on the right track? Meanwhile, I'll keep thinking about it. -
-
Re: Barrel puzzle
Thu, April 20, 2006 - 10:36 AMHi Juliana,
Yeah, it's the "infinity" problem I was worried about. Obviously, each time you repeat the search for the "up" glass, you'll hit it half the time, so after 10 attempts, the odds are less than 1 in a thousand (1 in 1024 to be exact) that the problem isn't solved. But theres a 1 in 2^1000000 chance it still wouldn't be over after a million operations.
A solution can never count on touching all the glasses, since with bad luck, you'll never hit one of them, so it has to be structured so that you'll either get all 4 up or all 4 down. You can, of course guarantee that you'll touch three of them.
The saving thing in the problem is that you don't have to know when you get to "solved". The instant the four glasses are the same, a bell rings. So a solution does not require that YOU know when a move has solved it: you just need a sequence of moves that's guaranteed to pass though a solution state. -
-
Re: Barrel puzzle
Thu, April 20, 2006 - 12:05 PMOk, now i have a plan that gets to the "ding" in three steps in almost any situation. But there's still one branching off of possibilities that leads to the infinity problem. (When at some point you may wind up with three of one and one of the other, and you know it. I'm not sure how to get out of that one without resorting to possible infinite spinning.)
Am I thinking in the right direction though, or should I switch gears? -
-
Re: Barrel puzzle
Thu, April 20, 2006 - 12:18 PMspoke a minute too soon... I *think* I can now get to the ding in two steps in most situations. But there's still the one possibility that leads to infinity, so I'm still stuck there. -
-
Re: Barrel puzzle
Thu, April 20, 2006 - 2:51 PMI'll give a hint, if you want. Don't scroll down if you don't want to see it.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Here's how to start:
Get three of them up (easy)
If the one you haven't touched was up, the bell rings and you're done, so the fourth one must be down, so the current configuration must be:
U
U U
D
Reach into an adjacent pair. If you happen to find the down, flip it, and you're done. Otherwise, you've got your hands on two up's so just turn one of them over. Now there are only two possible configurations:
U
U D
D
or
U
D D
U
Next, grab a pair of opposites. If they're the same, flip them both and you're done. If not, don't do anything.
Now what?
-
-
Re: Barrel puzzle
Thu, April 20, 2006 - 6:17 PMACKK!! Frustrating...but I like your cruel style.
I had actually gotten myself exactly as far as your hint goes (without looking at the hint) and finally decided to give up and read it. So I'm still stuck exactly where your hint ends! But I'm actually relieved you didn't put the answer in. Now that I know I'm on the right track I'll just keep tearing my hair out for a while longer... -
-
Re: Barrel puzzle
Thu, April 20, 2006 - 9:23 PMWhew...it suddenly just went from impossible to crystal clear. I'm glad you withheld the final steps.
so here's what I think will work in that instance where you're stuck with
UD
UD
(I'll hide my solution below, so I don't ruin it for someone else who might be reading this.)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
grab two adjacent glasses. If they're the same you can turn them both over. Ding.
if they're different then flip them both over.
Now you know you have:
UD
DU
grab any two opposites and flip them both over. Ding!
So it looks like the maximum steps needed to guarantee all same glasses is 6.
Does this sound right?
-
-
Re: Barrel puzzle
Fri, April 21, 2006 - 8:09 AMHey Juliana,
That's the best one I found. I doubt that it can be done any faster, but I haven't tried to prove it.
-
-
-
-
-
-
-
