[Guest]

You are one of 9 prisoners to be executed tomorrow. The wicked king, who we all know ejoys playing cruel games, puts the fate of all of you in YOUR hands. Tomorrow he will line each of the other 8 prisoners up side by side, and give them each a RED or BLACK hat. He tells you the hats will be split evenly, 4 RED and 4 BLACK, but in any order. No prisoner can see their own, nor the other prisoners hats, but they know what order they stand in line. (Left to right- 1st, 2nd, 3rd, etc.) The king will allow you to say ONLY one number, positive or negative between 0-32. (The positive and negative makes it much easier to work when solving) However the king has underestimated your abilities! Devise a plan to inform each prisoner the color of their hat with a single number.

Edited August 11, 2008 by EyesOfTheDead

[unreality]

so the range is -32 to 32?

[Guest]

Sorry to make it sound confusing, but the way I worded it has a poit as well

so the range is -32 to 32?

P.S.

Sorry if my posts are out of the norm. I am new to threads and forums :/

Edited August 11, 2008 by EyesOfTheDead

[Guest]

My first attept.. I need to buy 5 more numbers from the king, leaving -32 - 27.

[Guest]

Very interesting problem. Essentially you are given 6 bits of information and one additional state (perhaps null) and you have to reconstruct 8 bits of information. This is usually impossible but with the information that there are exactly 4 red hats, you are given two more bits... Now I just need to figure out how to use them.

[Guest]

You have to compress 70 possibilities into 65 states (66 if you count +0 and -0 )

[Guest]

Ok after racking my brain trying to come up with some complex code of red=3 black =5 and multiplying by position and adding or subtracting to get the answer i figured out it is a whole heck of a lot simpler than that i think the answer is

it's simple starting with bbbbrrrr and working the combos there are 32 then rrrrbbbb also 32 so make a list have them memorize it with the positive or negative number to the sequence

so do i get a cookie?

[Guest]

Ok after racking my brain trying to come up with some complex code of red=3 black =5 and multiplying by position and adding or subtracting to get the answer i figured out it is a whole heck of a lot simpler than that i think the answer is

it's simple starting with bbbbrrrr and working the combos there are 32 then rrrrbbbb also 32 so make a list have them memorize it with the positive or negative number to the sequence

so do i get a cookie?

I work out 72 different variations, not the 64 as you have stated

[Guest]

Ok so i went back and counted at i actually get 70 now must have gone to fast. but i don't see where I'm missing the other 2 i get

1 bbbbxxxx

4 bbbxxxxx

10 bbxxxxxx

20 bxxxxxxx

for a total of 35 x 2 = 70 hmmm must be too tired to count tonight although 70 makes sense since if you run 8 choose 4 through the calculator you get 70 so no answer yet

[Guest]

Ok so i went back and counted at i actually get 70 now must have gone to fast. but i don't see where I'm missing the other 2 i get

1 bbbbxxxx

4 bbbxxxxx

10 bbxxxxxx

20 bxxxxxxx

for a total of 35 x 2 = 70 hmmm must be too tired to count tonight although 70 makes sense since if you run 8 choose 4 through the calculator you get 70 so no answer yet

sorry.. that was my type.. I ment 70

[unreality]

isn't it P(8,4) which is monstrous, (1680)?

[Guest]

isn't it P(8,4) which is monstrous, (1680)?

No, because all the red hats are the same. (and all the black hats don't matter, they just take up whatever leftover space there is.)

Since you can reorder the red hats however you like the solution is the combination 8 C 4 = 70 instead of the permutation 8 P 4 = 1680

[Guest]

doesn't it say that it is 4 red and 4 black hats so how do u get

BBrrrrr

it would all ways have to be a combo for

4 r and 4 b

[bonanova]

My first attempt leaves it a toss-up.

First hat color is encoded in the sign - negative is red, positive is black.

Last hat is a given by the 4-4 split if the others are known.

It remains to identify hats 2-7 [6 hats] with a 5-bit integer [n<33].

If the hats 7 and 8 are the same color, identifying hats 2-6 does it.

Make red=0 and black=1 to get the binary representation of the number.

But with this strategy, if they're different they'll have to guess, with 50% success.

I have another idea which I'll share in another post after thinking a bit.

[Guest]

My first attempt leaves it a toss-up.

First hat color is encoded in the sign - negative is red, positive is black.

Last hat is a given by the 4-4 split if the others are known.

It remains to identify hats 2-7 [6 hats] with a 5-bit integer [n<33].

If the hats 7 and 8 are the same color, identifying hats 2-6 does it.

Make red=0 and black=1 to get the binary representation of the number.

But with this strategy, if they're different they'll have to guess, with 50% success.

I have another idea which I'll share in another post after thinking a bit.

Identify 6 hats and you have a good chance of winning (better than 50%) because there is a 3/7 chance that the last two hats are the same color, which could be determined by the last two people based on all the other hats. Then, provided you discuss first who will pick which colors in case of alternates (to prevent both from picking the same color) your 50% comes into play for the remaining 4/7 chance. Your final chance of success is 3/7 + (50% * 4/7) = 5/7, which really isn't too bad.

[bonanova]

This is closer, but...

Black hats are encoded as 1; red hats as zero.

Previous post suggests encoding hat 1 by the sign: red is negative, black is positive.

If hats 2-7 can be identified, hat 8 is given by the 4-4 distribution.

Problem is to identify 6 hats with a signed 5-bit number.

Note hats 2-7 have at least 2 and no more than 4 black hats.

The number thus can't be less than 3 or greater than 60.

But those 58 numbers can't be encoded in 6 bits.

Look more closely. Not all of those 58 numbers are possible.

If hats 1 and 8 have the same color, the colors of hats 2-7 are distributed 4-2.

⁴C₂ = 15 such combinations.

If hats 1 and 8 are different colors, the colors of hats 2-7 are distributed 3-3.

³C₃ = 20 such combinations.

In both cases we have 35 possible numbers.

These numbers can be listed and indexed with an integer in the range [1, 35].

But 5 bits [for each sign] only give us a range of [1, 32].

I'll leave it there for now.

Next?

[Guest]

This is closer, but...

Black hats are encoded as 1; red hats as zero.

Previous post suggests encoding hat 1 by the sign: red is negative, black is positive.

If hats 2-7 can be identified, hat 8 is given by the 4-4 distribution.

Problem is to identify 6 hats with a signed 5-bit number.

Note hats 2-7 have at least 2 and no more than 4 black hats.

The number thus can't be less than 3 or greater than 60.

But those 58 numbers can't be encoded in 6 bits.

Look more closely. Not all of those 58 numbers are possible.

If hats 1 and 8 have the same color, the colors of hats 2-7 are distributed 4-2.

⁴C₂ = 15 such combinations.

If hats 1 and 8 are different colors, the colors of hats 2-7 are distributed 3-3.

³C₃ = 20 such combinations.

In both cases we have 35 possible numbers.

These numbers can be listed and indexed with an integer in the range [1, 35].

But 5 bits [for each sign] only give us a range of [1, 32].

I'll leave it there for now.

Next?

Yes, correct. Also, you can pick up a miscellaneous additional state by remembering that zero (null) is a valid value. You still have the essential problem stated long before that you are trying to represent 70 possible states with 65 possible numbers.

[Guest]

Here's the answer:

Use the following numbers. There are 65 possibilities.

-32 bbbbrrrr

-31 bbbrbrrr

-30 bbbrrbrr

-29 bbbrrrbr

-28 bbbrrrrb

-27 bbrbbrrr

-26 bbrbrbrr

-25 bbrbrrbr

-24 bbrbrrrb

-23 bbrrbbrr

-22 bbrrbrbr

-21 bbrrbrrb

-20 bbrrrbrb

-19 bbrrrrbb

-18 brbbbrrr

-17 brbbrbrr

-16 brbbrrbr

-15 brbbrrrb

-14 brbrbbrr

-13 brbrbrbr

-12 brbrbrrb

-11 brbrrbbr

-10 brbrrrbb

-9 brrbbbrr

-8 brrbbrbr

-7 brrbbrrb

-6 brrrbbbr

-5 brrrbbrb

-4 brrrbrbb

-3 brrrrbbb

-2 rbbbbrrr

-1 rbbbrbrr

0 rbbbrrbr

1 rbbbrrrb

2 rbbrbbrr

3 rbbrbrbr

4 rbbrbrrb

5 rbbrrbbr

6 rbbrrbrb

7 rbbrrrbb

8 rbrbbbrr

9 rbrbbrbr

10 rbrbbrrb

11 rbrbrbbr

12 rbrbrbrb

13 rbrbrrbb

14 rbrrbbbr

15 rbrrbbrb

16 rbrrbrbb

17 rbrrrbbb

18 rrbbbbrr

19 rrbbbrbr

20 rrbbbrrb

21 rrbbrbbr

22 rrbbrbrb

23 rrbbrrbb

24 rrbrbbbr

25 rrbrbbrb

26 rrbrbrbb

27 rrbrrbbb

28 rrrbbbbr

29 rrrbbbrb

30 rrrbbrbb

31 rrrbrbbb

32 rrrrbbbb

Edited August 12, 2008 by check12

[Guest]

Here's the answer:

Use the following numbers. There are 65 possibilities.

-32 bbbbrrrr

-31 bbbrbrrr

-30 bbbrrbrr

-29 bbbrrrbr

-28 bbbrrrrb

-27 bbrbbrrr

-26 bbrbrbrr

-25 bbrbrrbr

-24 bbrbrrrb

-23 bbrrbbrr

-22 bbrrbrbr

-21 bbrrbrrb

-20 bbrrrbrb

-19 bbrrrrbb

-18 brbbbrrr

-17 brbbrbrr

-16 brbbrrbr

-15 brbbrrrb

-14 brbrbbrr

-13 brbrbrbr

-12 brbrbrrb

-11 brbrrbbr

-10 brbrrrbb

-9 brrbbbrr

-8 brrbbrbr

-7 brrbbrrb

-6 brrrbbbr

-5 brrrbbrb

-4 brrrbrbb

-3 brrrrbbb

-2 rbbbbrrr

-1 rbbbrbrr

0 rbbbrrbr

1 rbbbrrrb

2 rbbrbbrr

3 rbbrbrbr

4 rbbrbrrb

5 rbbrrbbr

6 rbbrrbrb

7 rbbrrrbb

8 rbrbbbrr

9 rbrbbrbr

10 rbrbbrrb

11 rbrbrbbr

12 rbrbrbrb

13 rbrbrrbb

14 rbrrbbbr

15 rbrrbbrb

16 rbrrbrbb

17 rbrrrbbb

18 rrbbbbrr

19 rrbbbrbr

20 rrbbbrrb

21 rrbbrbbr

22 rrbbrbrb

23 rrbbrrbb

24 rrbrbbbr

25 rrbrbbrb

26 rrbrbrbb

27 rrbrrbbb

28 rrrbbbbr

29 rrrbbbrb

30 rrrbbrbb

31 rrrbrbbb

32 rrrrbbbb

I think you're missing bbrrrbbr

[Guest]

No-one said you had to use whole numbers...

But seriously, I'm not convinced this one is doable. I'll be interested to see the answer.

The only thing running through my head is something like the +/- defines whether you have to start from the left or the right... but I don't think that will reduce the data needed.

[Guest]

You have to compress 70 possibilities into 65 states (66 if you count +0 and -0 )

Very good, you got the +0 and -0. Sorry I am still not doing well with the quotes!

I will change the first post to include that it must be WHOLE numbers. I didn't even think about that

Edited August 12, 2008 by EyesOfTheDead

[Guest]

except for

01010101 = -0?

10101010 = +0?

every possibility combination has a 001 or 110. so maybe reducing this to a smaller bunch of number??

[Guest]

If you pick a starting number ( picked stragetically) and add or subtract numbers from it .. just my thoughts

[Guest]

Oops. After reading through and re-reading the problem, I made a crucial error! One of the tricks I had was being able to say positive or negative zero. However, I somehow added 2 vales for zero twice. It was supposed to be 0-32 +or- = 68 values and another from simply saying "positive" or "negative" which the king might assume you mean zero. I meant to say more directly that the king would allow you to say "positive or negative" + "number"

I am extremely sorry for this, because you are all right, there are 70 possible values, I just meant for 4 of them to be tricky.

Sorry again!

The real thing I was looking for is how you all would make a sequence that each number would be most easily distinguished.

(Also, How do I edit posts that I have already edited?)

Edited August 12, 2008 by EyesOfTheDead

[Guest]

If the positive or negative informed the first prisoner of their hat color and the the next five were informed using a five bit binary number represented in base ten. i.e. you would assign red to 1 and black to 0 and rrbbb would be 11000=24. Then 50% of the time the last two hats would be the same color and would be identified correctly and 50% of the time a guess would be required which would be correct 50% of the time, adding up to a 75% chance of survival.

I feel like it is possible to guarantee survival so I for one am not done thinking on this puzzle.

[unreality]

I've figured out a solution that saves 5 for sure, with:

* 1/2 chance to save 5

* 1/8 chance to save 6

* 3/8 chance to save all 8