Author 
Topic: 8 treasure chests, can change 1 (Read 1152 times) 

Destiny
Newbie
Posts: 1


8 treasure chests, can change 1
« on: Aug 26^{th}, 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 26^{th}, 2016, 6:58am » 
Quote Modify

on Aug 26^{th}, 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 26^{th}, 2016, 6:58am by dudiobugtron » 
IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: 8 treasure chests, can change 1
« Reply #2 on: Aug 26^{th}, 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 26^{th}, 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: 7517


Re: 8 treasure chests, can change 1
« Reply #4 on: Aug 26^{th}, 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 26^{th}, 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 28^{th}, 2016, 7:12am » 
Quote Modify

Nice. And it works for 2^N1 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 28^{th}, 2016, 9:28am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



rmsgrey
Uberpuzzler
Gender:
Posts: 2846


Re: 8 treasure chests, can change 1
« Reply #6 on: Aug 28^{th}, 2016, 7:42am » 
Quote Modify

on Aug 28^{th}, 2016, 7:12am, towr wrote:Nice. And it works for 2^N1 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 2^{n}1, how do you deal with the times you'd want to turn the missing chest? For 2^{n}+1, there's no arrangement of the first 2^{n} chests that doesn't correspond to one of those chests being the desired answer, so how do you trigger a failover to the extra chest?


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: 8 treasure chests, can change 1
« Reply #7 on: Aug 28^{th}, 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: x_{0,10} = d p (pS_{2} ^ bT_{0,10})_{0,10} S_{2}, where x_{0,10} is a 0based decimal number of the chest with a treasure, recovered by P_{2} d is a decimal operator  turns its binary argument into a base10 number p is a parity mask operator, explained below is a turn operator, i S turns an item i in a set S S_{2} is a (base2) 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 T_{0,10} is a 0based decimal number of the chest with a treasure, given to P_{1} The formula says: P_{1} encodes the treasured chest number in binary for P_{2} Sample computation: 1) Let PC arrange the chests completely at random: 01101101 2) Number the chests righttoleft, 0based in decimal: 76543210 01101101 (== S_{2}) 3) PC points to a chest and tells P_{1}: "This one has the treasure". Heavy 1, number 5 in our notation. 4) P_{1} computes pS_{2} as follows: move righttoleft through S_{2}, if the bit in the current position is 0 then record it as log_{2}8bit long 0 in binary, otherwise record this position's decimal number in binary, also log_{2}8bit long (2^{i} && S_{2}, 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: pS_{2} = 010 5) P_{1} computes bT_{0,10} = 5_{0,10} = (101)_{2}. 6) P_{1} computes pS_{2} ^ bT_{0,10} = 010 ^ 101 = 111. 7) P_{1} computes (111)_{2} = 7_{0,10}. 8) P_{1} turns the chest number 7, the last one. 9) S_{2} = 11101101. 10) P_{2} computes pS_{2} = (101)_{2} = 5_{0,10} recovering the number of the chest with the treasure.

« Last Edit: Aug 28^{th}, 2016, 7:57am by rloginunix » 
IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: 8 treasure chests, can change 1
« Reply #8 on: Aug 28^{th}, 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 28^{th}, 2016, 9:27am » 
Quote Modify

on Aug 28^{th}, 2016, 7:42am, rmsgrey wrote:I need a bit more convincing of these two claims. For 2^{n}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^N1 are in the right configuration. Oops. (Would dropping that requirement open up a lot of other possible solutions?) Quote:For 2^{n}+1, there's no arrangement of the first 2^{n} chests that doesn't correspond to one of those chests being the desired answer, so how do you trigger a failover 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 28^{th}, 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 28^{th}, 2016, 10:10am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



rloginunix
Uberpuzzler
Posts: 1026


Re: 8 treasure chests, can change 1
« Reply #11 on: Aug 28^{th}, 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 28^{th}, 2016, 10:39pm » 
Quote Modify

on Aug 28^{th}, 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 graphcoloring, not 100%. Or do you mean it gives the best achievable score, but not necessarily 100%?

« Last Edit: Aug 28^{th}, 2016, 10:43pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



rloginunix
Uberpuzzler
Posts: 1026


Re: 8 treasure chests, can change 1
« Reply #13 on: Aug 29^{th}, 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 29^{th}, 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: 1026


Re: 8 treasure chests, can change 1
« Reply #15 on: Aug 29^{th}, 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: 1026


Re: 8 treasure chests, can change 1
« Reply #16 on: Aug 30^{th}, 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,zcoordinate, 1 bit per, 3 bits total. A parity mask of a cube then can be computed thus: for all the 1chests XOR the xcoordinates, ycoordinates, zcoordinates. The coordinates of the Tchest are known: XOR its components with the corresponding pieces of the mask = the coordinates of the chest to turn. P_{2} 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: 1026


Re: 8 treasure chests, can change 1
« Reply #17 on: Sep 2^{nd}, 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 stripfolding, 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 



