Author |
Topic: 8 treasure chests, can change 1 (Read 1460 times) |
|
Destiny
Newbie
Posts: 1
|
 |
8 treasure chests, can change 1
« on: Aug 26th, 2016, 5:35am » |
 Quote  Modify
|
After beating him at cards you and your partner given the chance to earn some treasure from the pirate captain if your wits or luck are good enough. To do it you will be shown 8 treasure chests, either with their front or their side facing you. The captain will point out one of them and say the treasure is in there. You then must turn one of the chests so its side is now facing instead of the front or vice versa. You must turn one and only one.
Your partner, not knowing the original layout of the chests, must look at them and say which chest has the treasure.
You have time to prepare beforehand with your partner. What's your strategy and how likely are you to get the treasure?
|
|
 IP Logged |
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: 8 treasure chests, can change 1
« Reply #1 on: Aug 26th, 2016, 6:58am » |
Quote Modify
|
on Aug 26th, 2016, 5:35am, Destiny wrote:| how likely are you to get the treasure? |
|
Very unlikely. Not because your strategy is bad, but because you should never trust a Pirate Captain!
|
| « Last Edit: Aug 26th, 2016, 6:58am by dudiobugtron » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: 8 treasure chests, can change 1
« Reply #2 on: Aug 26th, 2016, 7:03am » |
Quote Modify
|
Preliminary thoughts: 1) 8 is an exact power of two; 2) changing the position of one chest flips the parity - between odd and even.
Primitive case: two chests.
The possibilities are:
00
11
01
10
PC can put the treasure into either the first or the second chest - we do not know. Consequently, ahead of time we agree on a rule: if PC chooses the first chest then our objective is to make sure that 1 is in the first position.
1) If PC chooses the first chest then the possibilities are:
00 - turn the first chest: 10
11 - turn the second chest: 10 - you must turn a chest, I take it, but it does not matter
01 - turn the first chest: 11
10 - turn the second chest: 11
In all the cases the first chest is turned - hence, that is the chest where the treasure is.
By analogy, if PC chooses the second chest then ahead of time rule agreed upon is: if PC chooses the second chest then our objective is to make sure that not 1 is in the first position.
2) If PC chooses the second chest then the possibilities are:
00 - turn the second chest: 01
11 - turn the first chest: 01
01 - turn the second chest: 00
10 - turn the first chest: 00
In all the cases the first chest is not turned - hence, the treasure is in the second chest.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: 8 treasure chests, can change 1
« Reply #3 on: Aug 26th, 2016, 8:44am » |
Quote Modify
|
In the same vein, you might be able to do something with error correcting codes.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: 8 treasure chests, can change 1
« Reply #4 on: Aug 26th, 2016, 4:32pm » |
Quote Modify
|
Yep, error correcting codes. Or a parity trick.
Let's name the chests ABCDEFGH. Let's give them the value 1 if facing you, 0 if not.
Mentally turn the treasure chest.
Then find out which chest to change to make:
-> A+B+C+D = 0
-> A+B+E+F = 0
-> A+C+E+G = 0
(add modulo 2, and count the treasure chest state as reversed).
Each sum can be changed to zero by turning one of the 4 chest or left zero by changing one of the 4 remaining chests. Each sum removes half of the possibilities, leaving 1 chest that you can change to zero all 3 sums.
Then the 2nd player does the same sums. They are not necessarily zero for him because he didn't imagine the treasure chest turned. But by the same process he can find out which chest needs to be turned to zero all the sums. That must be the treasure chest.
That can easily be extended to 2^N chests.
|
| « Last Edit: Aug 26th, 2016, 4:34pm by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 8 treasure chests, can change 1
« Reply #5 on: Aug 28th, 2016, 7:12am » |
Quote Modify
|
Nice. And it works for 2^N-1 as well (as you can just pretend there's an extra box with fixed position) and 2^N+1 (without changing anything to the procedure the second player can spot when the pick isn't in the first 2^N).
But how about other numbers? Can we get a perfect score on 6? 10? 11?
|
| « Last Edit: Aug 28th, 2016, 9:28am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: 8 treasure chests, can change 1
« Reply #6 on: Aug 28th, 2016, 7:42am » |
Quote Modify
|
on Aug 28th, 2016, 7:12am, towr wrote:| Nice. And it works for 2^N-1 as well (as you can just pretend there's an extra box with fixed position) and 2^N+1 (without changing anything to the procedure the second player can spot when the pick isn't in the first 2^N). |
|
I need a bit more convincing of these two claims.
For 2n-1, how do you deal with the times you'd want to turn the missing chest?
For 2n+1, there's no arrangement of the first 2n chests that doesn't correspond to one of those chests being the desired answer, so how do you trigger a fail-over to the extra chest?
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: 8 treasure chests, can change 1
« Reply #7 on: Aug 28th, 2016, 7:44am » |
Quote Modify
|
[e]
Sorry every one - while I was typing my follow up to Grimbal's reply, towr and rmsgrey posted theirs. Connect this post to "Reply #4", I am not addressing towr's question here.
[/e]
Nice.
Same idea expressed a bit differently, in closed form with operators, and computationally more intensive:
x0,10 = d p  (pS2 ^ bT0,10)0,10  S2, where
x0,10 is a 0-based decimal number of the chest with a treasure, recovered by P2
d is a decimal operator - turns its binary argument into a base-10 number
p is a parity mask operator, explained below
is a turn operator, i S turns an item i in a set S
S2 is a (base-2) set of 0s and 1s - a collection of chests
b is a binary operator - turns its decimal argument into a string of 0s and 1s
^ is a bitwise XOR, exclusive OR, operator
T0,10 is a 0-based decimal number of the chest with a treasure, given to P1
The formula says: P1 encodes the treasured chest number in binary for P2
Sample computation:
1) Let PC arrange the chests completely at random:
01101101
2) Number the chests right-to-left, 0-based in decimal:
76543210
01101101 (== S2)
3) PC points to a chest and tells P1: "This one has the treasure". Heavy 1, number 5 in our notation.
4) P1 computes pS2 as follows:
move right-to-left through S2, if the bit in the current position is 0 then record it as log28-bit long 0 in binary, otherwise record this position's decimal number in binary, also log28-bit long (2i && S2, for i>0):
:0: 000
1: 000
2: 010
3: 011
4: 000
5: 101
6: 110
7: 000
XOR the bits in each column. We remember that XORing multiple boolean variables is equivalent to modulo 2 arithmetic, result:
pS2 = 010
5) P1 computes bT0,10 = 50,10 = (101)2.
6) P1 computes pS2 ^ bT0,10 = 010 ^ 101 = 111.
7) P1 computes (111)2 = 70,10.
8) P1 turns the chest number 7, the last one.
9) S2 = 11101101.
10) P2 computes pS2 = (101)2 = 50,10 recovering the number of the chest with the treasure.
|
| « Last Edit: Aug 28th, 2016, 7:57am by rloginunix » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: 8 treasure chests, can change 1
« Reply #8 on: Aug 28th, 2016, 8:39am » |
Quote Modify
|
Call me one crazy bear, crazy bear, but these are the moments in math that make our hearts race and pound. So here we are, discussing things in "Strip Teeze", in 'compsci' ...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 8 treasure chests, can change 1
« Reply #9 on: Aug 28th, 2016, 9:27am » |
Quote Modify
|
on Aug 28th, 2016, 7:42am, rmsgrey wrote:I need a bit more convincing of these two claims.
For 2n-1, how do you deal with the times you'd want to turn the missing chest? |
|
Well, I was thinking that all the parity checks never include the 2^Nth chest.
But I've neglected that you need to turn at least one chest. Without that requirement, it would work, cause you'd never need to touch the last chest; but unfortunately now you need to turn it if the first 2^N-1 are in the right configuration.
Oops.
(Would dropping that requirement open up a lot of other possible solutions?)
Quote:| For 2n+1, there's no arrangement of the first 2n chests that doesn't correspond to one of those chests being the desired answer, so how do you trigger a fail-over to the extra chest? |
|
My thinking was that player one always introduces an error that player 2 then correct to find the chest. Buuuuut, that's incorrect. For the same reason as earlier, among possible other things.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 8 treasure chests, can change 1
« Reply #10 on: Aug 28th, 2016, 10:07am » |
Quote Modify
|
In general, a solution corresponds to coloring the vertices in a graph, where each vertex is a state and two states are connected when there's a single turn transition between them. (The color corresponds to which chest has the treasure.) The outgoing edges for a vertex must lead to a K different colored vertices (where K is the number of boxes). Since there's only K outgoing edges, that means they're all different. And I daresay symmetry means that K must therefore divide 2^K to be able to get a perfect score, in which case K can only be a power of two.
If we drop the requirement that you must turn at least one box (flip at least one bit), then all vertices can have an optional extra edge (to the state itself) or use it to replace another, allowing for solutions for other values of K.
|
| « Last Edit: Aug 28th, 2016, 10:10am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: 8 treasure chests, can change 1
« Reply #11 on: Aug 28th, 2016, 2:16pm » |
Quote Modify
|
In an attempt to clear up the confusion: I think that the procedure described in "Reply #7" does work for any number of chests, not necessarily an exact power of two. Reason for confusion: asynchronous communication.
Time line this morning:
- I log in, start typing
- towr posts "Reply #5"
- rmsgrey posts "Reply #6"
- I post "Reply #7" not knowing about #5 and #6, but then see #5 and #6
Since answering towr's "Reply #5" question was never my intention, it was just a coincidence, I modify "Reply #7" saying so - the only honest thing to do. Besides, when I was working on the procedure I thought about exact powers of two only.
Later I read the question and realized that the procedure works for an arbitrary number of chests, "Reply #8". But I shall keep "Reply #7" as is - changing it now will only add to confusion.
Sorry for the mess.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 8 treasure chests, can change 1
« Reply #12 on: Aug 28th, 2016, 10:39pm » |
Quote Modify
|
on Aug 28th, 2016, 2:16pm, rloginunix wrote:| Later I read the question and realized that the procedure works for an arbitrary number of chests, "Reply #8". |
|
If it works for any number of chests, would you mind applying it to K=3?
Because I can only get a 20/24 score using graph-coloring, not 100%. Or do you mean it gives the best achievable score, but not necessarily 100%?
|
| « Last Edit: Aug 28th, 2016, 10:43pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: 8 treasure chests, can change 1
« Reply #13 on: Aug 29th, 2016, 5:33am » |
Quote Modify
|
You are right, towr. I now see why I rushed to conclusion. For three chests the procedure works for some arrangements which I happen to test:
111
Parity mask is 011, treasured chest is 010, chest to turn is 011 xor 010 = 001.
It also works for:
010
Parity mask is 001, treasured chest is 001, chest to turn is 001 xor 001 = 000.
The arrangement that the procedure does not work for is:
010
since the chest to turn comes out to 011, the one we do not have. Hm, I guess I did not test this one. My bad. It looked so attractive, that's why my pulse raised,  .
I wonder if it can be tweaked.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 8 treasure chests, can change 1
« Reply #14 on: Aug 29th, 2016, 8:54am » |
Quote Modify
|
I doubt any solution can be tweaked to work all the time (unless you drop the constraint that you need to flip exactly one bit).
From state 000 player one needs to change it to either 001, 010, or 100 and they all have to represent a different place for the treasure chest. But then 011 implies 111 must be the same as 100, but 110 implies 111 must be the same as 001, and that can't be true because they are different.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: 8 treasure chests, can change 1
« Reply #15 on: Aug 29th, 2016, 11:08am » |
Quote Modify
|
Yeah. I was thinking about Hamming codes - works for any number of bits. But they have the luxury of inserting parity bits at exact powers of 2 and we have a fixed size string.
(driving from NY to Boston right now, can't really do much)
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: 8 treasure chests, can change 1
« Reply #16 on: Aug 30th, 2016, 6:23am » |
Quote Modify
|
Was thinking. Not only 8 is an exact power of 2, it is also a perfect cube, 2x2x2. We all, I gather, silently assumed a linear geometry of the chests while, in fact, these 8 ones can be folded into a cube. Each chest then will have an x,y,z-coordinate, 1 bit per, 3 bits total.
A parity mask of a cube then can be computed thus: for all the 1-chests XOR the x-coordinates, y-coordinates, z-coordinates. The coordinates of the T-chest are known: XOR its components with the corresponding pieces of the mask = the coordinates of the chest to turn. P2 computes the mask of the cube.
This works for 8, 64, 512, ...
Now, 64 also doubles up as a perfect square ...
This is an obfuscation of a straight line but may be of interest.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: 8 treasure chests, can change 1
« Reply #17 on: Sep 2nd, 2016, 8:37am » |
Quote Modify
|
My last two cents: referring to 'Strip Teeze' earlier, I was hinting at one of the underlying commonalities between these two problems - identity transformation, a transformation which, when applied twice in succession, restores the original. In 'Strip Teeze' it is a particular strip-folding, in this problem it is the mod 2 arithmetic (or bitwiise XOR).
In geometry - an inversion with respect to a circle in a real plane, for example. A point in the circle of inversion is thrown out of it and conversely.
Even more amazing is the commonality between the procedure suggested by Grimbal and one of the physical models in 'Strip Teeze'. However, I will wait for some one willing to step forward and discuss the modelling in 'Strip Teeze', which may be never, so for public record: skipping the powers of two.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print