

Title: 8 treasure chests, can change 1 Post by Destiny on Aug 26^{th}, 2016, 5:35am 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? 

Title: Re: 8 treasure chests, can change 1 Post by dudiobugtron on Aug 26^{th}, 2016, 6:58am on 08/26/16 at 05:35:13, Destiny wrote:
[hide]Very unlikely. Not because your strategy is bad, but because you should never trust a Pirate Captain![/hide] 

Title: Re: 8 treasure chests, can change 1 Post by rloginunix on Aug 26^{th}, 2016, 7:03am Preliminary thoughts: [hide]1) 8 is an exact power of two; 2) changing the position of one chest flips the parity  between odd and even[/hide]. 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. 

Title: Re: 8 treasure chests, can change 1 Post by towr on Aug 26^{th}, 2016, 8:44am In the same vein, you might be able to do something with error correcting codes. 

Title: Re: 8 treasure chests, can change 1 Post by Grimbal on Aug 26^{th}, 2016, 4:32pm Yep, error correcting codes. Or a parity trick. [hide]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.[/hide] 

Title: Re: 8 treasure chests, can change 1 Post by towr on Aug 28^{th}, 2016, 7:12am Nice. But how about other numbers? Can we get a perfect score on 6? 10? 11? 

Title: Re: 8 treasure chests, can change 1 Post by rmsgrey on Aug 28^{th}, 2016, 7:42am on 08/28/16 at 07:12:14, towr 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? 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? 

Title: Re: 8 treasure chests, can change 1 Post by rloginunix on Aug 28^{th}, 2016, 7:44am [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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/tau.gif (pS_{2} ^ bT_{0,10})_{0,10} http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subset.gif S_{2}, where [hide]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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/tau.gif is a turn operator, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/tau.gif i http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subset.gif 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}[/hide] 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: [hide]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)[/hide]: [hide]:0: 000 1: 000 2: 010 3: 011 4: 000 5: 101 6: 110 7: 000[/hide] [hide]XOR the bits in each column. We remember that XORing multiple boolean variables is equivalent to modulo 2 arithmetic, result: pS_{2} = 010[/hide] 5) P_{1} computes bT_{0,10} = [hide]5_{0,10} = (101)_{2}[/hide]. 6) P_{1} computes pS_{2} ^ bT_{0,10} = [hide]010 ^ 101 = 111[/hide]. 7) P_{1} computes [hide](111)_{2} = 7_{0,10}[/hide]. 8) P_{1} turns the chest number [hide]7, the last one[/hide]. 9) S_{2} = [hide]11101101[/hide]. 10) P_{2} computes pS_{2} = [hide](101)_{2} = 5_{0,10}[/hide] recovering the number of the chest with the treasure. 

Title: Re: 8 treasure chests, can change 1 Post by rloginunix on Aug 28^{th}, 2016, 8:39am 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' ... 

Title: Re: 8 treasure chests, can change 1 Post by towr on Aug 28^{th}, 2016, 9:27am on 08/28/16 at 07:42:17, rmsgrey wrote:
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:


Title: Re: 8 treasure chests, can change 1 Post by towr on Aug 28^{th}, 2016, 10:07am 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. 

Title: Re: 8 treasure chests, can change 1 Post by rloginunix on Aug 28^{th}, 2016, 2:16pm 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. 

Title: Re: 8 treasure chests, can change 1 Post by towr on Aug 28^{th}, 2016, 10:39pm on 08/28/16 at 14:16:26, rloginunix wrote:
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%? 

Title: Re: 8 treasure chests, can change 1 Post by rloginunix on Aug 29^{th}, 2016, 5:33am 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 [hide]011[/hide], treasured chest is 010, chest to turn is [hide]011 xor 010 = 001[/hide]. It also works for: 010 Parity mask is [hide]001[/hide], treasured chest is 001, chest to turn is [hide]001 xor 001 = 000[/hide]. 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. 

Title: Re: 8 treasure chests, can change 1 Post by towr on Aug 29^{th}, 2016, 8:54am 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. 

Title: Re: 8 treasure chests, can change 1 Post by rloginunix on Aug 29^{th}, 2016, 11:08am 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) 

Title: Re: 8 treasure chests, can change 1 Post by rloginunix on Aug 30^{th}, 2016, 6:23am 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: [hide]for all the 1chests XOR the xcoordinates, ycoordinates, zcoordinates[/hide]. The coordinates of the Tchest are known: [hide]XOR its components with the corresponding pieces of the mask[/hide] = 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. 

Title: Re: 8 treasure chests, can change 1 Post by rloginunix on Sep 2^{nd}, 2016, 8:37am My last two cents: referring to 'Strip Teeze' earlier, I was hinting at one of the underlying commonalities between these two problems  [hide]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)[/hide]. 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: [hide]skipping the powers of two[/hide]. 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 