wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 8 treasure chests, can change 1
        
(Message started by: Destiny on Aug 26th, 2016, 5:35am)
Title: 8 treasure chests, can change 1
Post by Destiny on Aug 26th, 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 26th, 2016, 6:58am

on 08/26/16 at 05:35:13, Destiny wrote:
how likely are you to get the treasure?

[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 26th, 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 26th, 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 26th, 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 28th, 2016, 7:12am
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?
Title: Re: 8 treasure chests, can change 1
Post by rmsgrey on Aug 28th, 2016, 7:42am

on 08/28/16 at 07:12:14, 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?
Title: Re: 8 treasure chests, can change 1
Post by rloginunix on Aug 28th, 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:

x0,10 = d p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/tau.gif (pS2 ^ bT0,10)0,10 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subset.gif S2, where

[hide]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
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
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[/hide]

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:

[hide]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)[/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:

pS2 = 010[/hide]

5) P1 computes bT0,10 = [hide]50,10 = (101)2[/hide].

6) P1 computes pS2 ^ bT0,10 = [hide]010 ^ 101 = 111[/hide].

7) P1 computes [hide](111)2 = 70,10[/hide].

8) P1 turns the chest number [hide]7, the last one[/hide].

9) S2 = [hide]11101101[/hide].

10) P2 computes pS2 = [hide](101)2 = 50,10[/hide] recovering the number of the chest with the treasure.
Title: Re: 8 treasure chests, can change 1
Post by rloginunix on Aug 28th, 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 28th, 2016, 9:27am

on 08/28/16 at 07:42:17, 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.
Title: Re: 8 treasure chests, can change 1
Post by towr on Aug 28th, 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 28th, 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 28th, 2016, 10:39pm

on 08/28/16 at 14:16:26, 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%?
Title: Re: 8 treasure chests, can change 1
Post by rloginunix on Aug 29th, 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 29th, 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 29th, 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 30th, 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,z-coordinate, 1 bit per, 3 bits total.

A parity mask of a cube then can be computed thus: [hide]for all the 1-chests XOR the x-coordinates, y-coordinates, z-coordinates[/hide]. The coordinates of the T-chest are known: [hide]XOR its components with the corresponding pieces of the mask[/hide] = 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.
Title: Re: 8 treasure chests, can change 1
Post by rloginunix on Sep 2nd, 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 strip-folding, 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 © 2000-2004 Yet another Bulletin Board