Author |
Topic: Arrange hidden coins on a table (Read 2737 times) |
|
Whymme
Guest
|
I did a search and did not find this question in the forums. Forgive me if it has been posted already anyway.
It's a nice puzzle. I changed the questioning at the end a bit, because the problem as I heard it gave too much away.
The set-up:
A square table, each side equal to all the others, rests on one leg that supports the table in the middle. The table can rotate around the axis of the leg.
On each corner of the table is a square box with a lid. The boxes are identical and there is no way to distinguish one box from another.
Inside each box is a coin. A normal coin, one side showing heads and the other side showing tails. At the start of the game, at least one coin is showing heads and at least one is showing tails.
The game:
On your turn, you can open one or two boxes and, if you want to, turn one or both coins you have uncovered. Then you close the lids again. Turn is over.
You get blindfolded and the table is spun around a number of times (though not necessarily full turns). If you marked one or more boxes or the table, that mark is removed.
The blindfold is taken off and a second turn begins. At the start of the turn you have no way of identifying which boxes you opened last time - they all are the same.
As soon as all coins are faced the same way (either all showing heads or all showing tails), a signal sounds and the game is over. You have won.
The question: Assuming that you can pick an optimal strategy, what is the probability that you win the game in fewer than ten turns? And in fewer than eight?
Whymme
|
|
 IP Logged |
|
|
|
asterix
Guest
|
 |
Re: Arrange hidden coins on a table
« Reply #1 on: Oct 2nd, 2004, 5:04pm » |
 Quote  Modify
 Remove
|
I think the worst case scenario is a solution in 5 moves.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: Arrange hidden coins on a table
« Reply #2 on: Oct 2nd, 2004, 5:20pm » |
Quote Modify
|
I think 6 turns are enough.
I will assume the table signals the end only after we finished a turn.
(I believe it was presented already as some problem with a round spinning room or spinning column with holes)
>>
1. choose 2 opposite boxes and turn the coins to H
2. choose 2 adjacent boxes and turn the coins to H
-> if the game is not finished, there are 3H and 1T.
3. choose 2 adjacent boxes.
- if there is a T, turn it to H -> done
- else, turn one to T -> we now have 2H and 2T
4. choose 2 opposites.
- If they are same, turn them both -> done.
- else, you know the Ts are adjacent.
5. choose 2 adjacent.
- if they are same, turn them both -> done.
- else, turn both coins. -> the Ts and the Hs are now opposite.
6. choose 2 opposites, and turn the coins. This should conclude the game in the worst case.
Maybe there is a way to save 1 or 2 steps.
<<
|
| « Last Edit: Oct 2nd, 2004, 5:21pm by Grimbal » |
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Arrange hidden coins on a table
« Reply #3 on: Oct 2nd, 2004, 8:45pm » |
Quote Modify
|
Quote:4. choose 2 opposites.
- If they are same, turn them both -> done.
- else, you know the Ts are adjacent.
|
|
After the 4th turn we have
TTTT (done)
OR
HHHH (done)
OR
THTH (or HTHT)
In the last case, choosing 2 opposite coins will win in just 5 turns.
Quote:| The question: Assuming that you can pick an optimal strategy, what is the probability that you win the game in fewer than ten turns? And in fewer than eight? |
|
Rather, we may ask "With optimal play, what is the expected number of turns required to win?"
I make it 77/32 = 2.40625
(I don't think this belongs in Hard.)
|
| « Last Edit: Oct 3rd, 2004, 7:08am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Arrange hidden coins on a table
« Reply #4 on: Oct 3rd, 2004, 5:13am » |
Quote Modify
|
on Oct 2nd, 2004, 8:45pm, THUDandBLUNDER wrote:(I don't think this belongs in Hard.)
|
|
Maybe, you will find the following generalization more challenging: 
Now you play the game with n-gonal table, and are allowed to open up to k boxes.
1. Find a winning strategy for n=5, k=2.
2. For what combinations of n and k the winning strategy exists?
3. When such a strategy exists, what is the minimal guaranteed number of moves to win?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Arrange hidden coins on a table
« Reply #5 on: Oct 3rd, 2004, 9:11am » |
Quote Modify
|
on Oct 2nd, 2004, 8:45pm, THUDandBLUNDER wrote:
After the 4th turn we have
TTTT (done)
OR
HHHH (done)
OR
THTH (or HTHT)
|
|
No. After turn 4, we have HHTT (or similar by rotation).
turn 5 changes HHTT to HTHT,
turn 6 concludes.
|
|
IP Logged |
|
|
|
Whhymme
Guest
|
|
Re: Arrange hidden coins on a table
« Reply #6 on: Oct 3rd, 2004, 10:00am » |
Quote Modify
Remove
|
If this riddle doesn't belong in Hard, feel free to move it.
As for the question: I was asked the question: "Can you solve it in a limited number of steps. If yes, how? If no, why not?" That question already indicates that the answer should be "yes". I didn't want to give such a clue in the question, so I tried a slightly misleading one. I hope you don't mind that 
Grimbal's solution can be optimised. I'm sure that you want to find it out for yourselves, so I'll hide the answer.
3. Don't take adjacent, but opposite boxes. If one of them is T, flip it - you've won. If not, flip one coin to T. Now you have
HT
HT
4. Take adjacent boxes. If they're the same, flip both - you've won. If not, still flip both. You now have
HT
TH
5. Take opposite boxes and flip the coins.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Arrange hidden coins on a table
« Reply #7 on: Oct 3rd, 2004, 10:11am » |
Quote Modify
|
To begin with we have {? ? ? ?}
1) Choose 2 opposite boxes and turn the coins to H.
We now have {? H ? H}
If the referee does not stop the game we
2) choose 2 adjacent boxes and turn the coins to H.
We now have {? H H H}
If the referee does not stop the game, we know we have {T H H H} and we
3) take two opposite bottles.
If one is T turn it over; so that we have {H H H H} and we are done.
Else if they are both H turn one over; so that we are left with {T T H H}
4) choose two adjacent bottles and turn them over.
If they were H H, we have {T T T T} and we are done.
Else if they were T T, we have {H H H H} and we are done.
Else we have {T H T H}
5) take two opposite bottles and turn them over, and we are done.
|
| « Last Edit: Oct 3rd, 2004, 11:06am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Arrange hidden coins on a table
« Reply #8 on: Oct 3rd, 2004, 11:28am » |
Quote Modify
|
Ah, like this, OK. It was my step 3 that was useless.
|
|
IP Logged |
|
|
|
asterix
Guest
|
|
Re: Arrange hidden coins on a table
« Reply #9 on: Oct 3rd, 2004, 11:47am » |
Quote Modify
Remove
|
To the generalized question, I would be very surprised if n=5, k=2 has a guaranteed solution. Two requirements of any solution are:
1. You must reach a position where the next move guarantees victory. That will not happen when k<n/2.
2. You must force a viewing of all but one coin. If 2 coins are never seen, they could be opposites. When n=6, I don't see how you can do that if k<4. I'm going to take a guess here that a solution requires k=> 2n/3
|
|
IP Logged |
|
|
|
asterix
Guest
|
|
Re: Arrange hidden coins on a table
« Reply #10 on: Oct 3rd, 2004, 4:11pm » |
Quote Modify
Remove
|
My guess about the limits was, of course, ridiculous. Let's try again. If I'm correct the minimum k for each n is
n:k
2:2
3:2
4:2
5:3
6:4
7:4
8:4
9:5
10:6
11:6
12:6
13:7
14:8
15:8
16:8
I think I see a pattern. Why, I don't know. Maybe someone else can fill in the number of turns required for each n.
|
|
IP Logged |
|
|
|
asterix
Guest
|
|
Re: Arrange hidden coins on a table
« Reply #11 on: Oct 3rd, 2004, 4:15pm » |
Quote Modify
Remove
|
duh, I know n=2, k=1.
The only times I regret not being registered is when it's too late.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Arrange hidden coins on a table
« Reply #12 on: Oct 4th, 2004, 9:35am » |
Quote Modify
|
I am not sure about 5:3. I don't see any position that is such that you are sure to finish in one move.
|
|
IP Logged |
|
|
|
asterix
Guest
|
|
Re: Arrange hidden coins on a table
« Reply #13 on: Oct 4th, 2004, 1:00pm » |
Quote Modify
Remove
|
I should have explained that I was just working on the first step of figuring out how many you need to make sure that you have seen every coin but one.
Obviously, for a position of certain victory, all the coins of one orientation must be equally spaced around the table. So when n is prime there's no solution better than n-1.
I think the other n's should all have a better solution than that, but probably not as good as the numbers I cited, except in the case of 6:4.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Arrange hidden coins on a table
« Reply #14 on: Oct 5th, 2004, 9:00am » |
Quote Modify
|
on Oct 2nd, 2004, 5:20pm, Grimbal wrote:| (I believe it was presented already as some problem with a round spinning room or spinning column with holes) |
|
I certainly remember doing a fair amount of analysis on this problem in a different guise - a pillar in the center of a chamber which is slowly flooding with water has four holes, each of which has a lever inside. Our hero is trapped in the room, and faces drowning in 5 minutes. Each time the hero reaches into one or more holes, a sensor detects his hand, and, once his hand is removed, all four holes seal, and, if the levers match, the trap disarms and releases him; if the levers don't match, the interior mechanism spins for 50 seconds then the holes reopen...
On the other hand, the search function hasn't turned up anything for me either.
One of the points raised last time I discussed this one was that it can never be the right move (if you're seeking to minimise worst case) to pick opposite boxes twice in a row or adjacent boxes twice in a row - you risk getting the same pair you had last time - which almost always means you've wasted a turn completely. There are situations where getting the same pair twice can give you additional information, but the other way of pairing is always better in the worst case. This should generalise to never picking the same combination twice in a row (except for k=n-1)
The general consensus reached was that the minimum k for the winning move for a given n was (p-1)n/p where p is the smallest prime factor of n. I think I managed to come up with a solution for n=8 with k=4, but I can't remember the details.
I can't remember anyone coming up with general minimum time solutions or proving that a finishing move position is always achievable from a position with one tail and n-1 heads (say) given k is whichever is larger of the minimum required to give a "spanning set" of moves (a set that is guaranteed to see n-1 different coins) and the number required to make the finishing move.
|
|
IP Logged |
|
|
|
Whymme
Guest
|
|
Re: Arrange hidden coins on a table
« Reply #15 on: Oct 5th, 2004, 4:45pm » |
Quote Modify
Remove
|
on Oct 5th, 2004, 9:00am, rmsgrey wrote:
One of the points raised last time I discussed this one was that it can never be the right move (if you're seeking to minimise worst case) to pick opposite boxes twice in a row or adjacent boxes twice in a row - you risk getting the same pair you had last time - which almost always means you've wasted a turn completely. There are situations where getting the same pair twice can give you additional information, but the other way of pairing is always better in the worst case. This should generalise to never picking the same combination twice in a row (except for k=n-1) |
|
Not completely true, I'm afraid. With the puzzle at hand, your first two turns have to be adjacent and opposite, but it doesn't matter (much) in which sequence you do this. So either adjacent-opposite or opposite-adjacent is good. The third move has to be opposite, though, or you're wasting a turn.
Nitpick: It is slightly better to first pick opposites and turn the coins heads up, for instance. If you open a box on the second turn and see a coin with tails up, you can always win by taking the box opposite. That doesn't work when you first pick adjacent boxes.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Arrange hidden coins on a table
« Reply #16 on: Oct 6th, 2004, 1:56am » |
Quote Modify
|
on Oct 5th, 2004, 9:00am, rmsgrey wrote:| The general consensus reached was that the minimum k for the winning move for a given n was (p-1)n/p where p is the smallest prime factor of n. |
|
Did you mean p is the largest prime factor? If so, then it’s the correct answer.
Quote:I think I managed to come up with a solution for n=8 with k=4, but I can't remember the details.
I can't remember anyone coming up with general minimum time solutions or proving that a finishing move position is always achievable from a position with one tail and n-1 heads (say) given k is whichever is larger of the minimum required to give a "spanning set" of moves (a set that is guaranteed to see n-1 different coins) and the number required to make the finishing move. |
|
There exists a general strategy that solves the combination (n, (p-1)n/p) in at most m(m+1) moves, where m is the number of prime factors of n. For the case (8, 4) this gives 3*4 = 12 moves. In general, it's not optimal.
The simpler case is (6, 4). Can you device a winning strategy in 6 moves?
|
| « Last Edit: Oct 6th, 2004, 5:39am by Barukh » |
IP Logged |
|
|
|
asterix
Guest
|
|
Re: Arrange hidden coins on a table
« Reply #17 on: Oct 6th, 2004, 8:12am » |
Quote Modify
Remove
|
I think I can do 6:4 in five moves.
Check 1-4, make them all H: HHHH??
Check 1,2,3,5, make them H: HHHHHT or game over
Check 1,2,3,5, if all H make 1,3,5 T: THTHTT or game over
Check 1-4, if you only see only one H, flip 1 T to H to make them alternating: THTHTH or game over
Check 1,3,5: game over
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Arrange hidden coins on a table
« Reply #18 on: Oct 6th, 2004, 11:58am » |
Quote Modify
|
on Oct 6th, 2004, 1:56am, Barukh wrote:
Did you mean p is the largest prime factor? If so, then it’s the correct answer.
|
|
I said smallest, and I meant smallest. For instance, with 6, taking p=2 gives 3; p=3 gives 4. It is possible to play a winning move by picking 3 of the 6 boxes from the position HTHTHT - what may be impossible is setting up the winning move.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Arrange hidden coins on a table
« Reply #19 on: Oct 6th, 2004, 12:05pm » |
Quote Modify
|
on Oct 5th, 2004, 4:45pm, Whymme wrote:
Nitpick: It is slightly better to first pick opposites and turn the coins heads up, for instance. If you open a box on the second turn and see a coin with tails up, you can always win by taking the box opposite. That doesn't work when you first pick adjacent boxes. |
|
I was working under the assumption that you picked your boxes first, then opened them. If you're allowed to pick your second (or subsequent) boxes based on what you open in the first box(es) on each turn, then the moves are more complicated than just choosing "opposite" or "adjacent" in advance, and the simple theoretical argument against repeating the same pattern of boxes on two consecutive moves fails for the simple reason that you can guarantee you aren't opening the same pair of boxes despite opening the same pattern.
[e]
And, yes, I should have said that a strategy that repeats the same pattern on consecutive moves is never better than all those which don't. It looks like you can always find a joint-optimal (assuming you pick all your boxes for each move at the same time) solution where the last move to force all but one to be H is the same as the optimal first move to solve from the single-T position.
If you allow boxes to be opened between choices, then I think the optimal opening for (6,4) is 1245 followed by 123X with X opposite an opened T guaranteeing victory.
[/e]
|
| « Last Edit: Oct 6th, 2004, 12:31pm by rmsgrey » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Arrange hidden coins on a table
« Reply #20 on: Oct 6th, 2004, 12:11pm » |
Quote Modify
|
Speaking of last time I met this puzzle, the hypothesis was formed that any "spanning set" of moves (a set of moves that betwen them leave at most one coin unseen) that included a finishing move would be enough to give a solution. I don't think it was decided either way whether it was true.
[e]
For stronger hypotheses:
A universally least time solution can be found just using moves from a given spanning set that includes a finishing move.
A solution can be found by repeating the same sequence of length n, of n distinct moves (which come from a spanning set which includes a finishing move).
The combination of the above - a least time solution can be found which only uses a sequence of length n of n-distinct moves, all from a given spanning set which includes a finishing move.
If any or all of the hypotheses prove false, they can be weakened by requiring all moves in the legal set to involve k boxes.
And, just to clarify, by "move" I actually just mean a choice of pattern of boxes to open. What you do with the coins you reveal doesn't distinguish between moves. And I'm still assuming that you pick your pattern, then open the boxes, then fiddle wih the coins, then the umpire decides whether you've won.
[/e]
|
| « Last Edit: Oct 6th, 2004, 12:52pm by rmsgrey » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Arrange hidden coins on a table
« Reply #21 on: Oct 8th, 2004, 6:42pm » |
Quote Modify
|
I've just spotted that, for the (4,2) game, if the first move is adjacent, then on the second move, the opposite boxes are both H when you open them, you can save a move by pretending it was move 3...
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Arrange hidden coins on a table
« Reply #22 on: Oct 8th, 2004, 8:39pm » |
Quote Modify
|
on Oct 6th, 2004, 12:11pm, rmsgrey wrote:Speaking of last time I met this puzzle, the hypothesis was formed that any "spanning set" of moves (a set of moves that betwen them leave at most one coin unseen) that included a finishing move would be enough to give a solution. I don't think it was decided either way whether it was true.
[...]
|
|
OK, I've managed to disprove the hypothesis (and hence all the stronger ones) and in the process (probably) prove k=(p-1)n/p (where p is the largest prime factor) as a lower bound. Incidentally, I've solved (10, in 5 moves.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print