http://answers.yahoo.com/question/?qid=2...
"Please take your sits around the table
"For your valuable service I decided to reward you according to following procedure:
"My court jester will mark either red or blue spot on the forehead of each of you, according to random 50/50 coin toss, invisible to the person being marked, but clearly visible to the other 6 of you. The jester will also hand you a piece of paper with your name written on it, and a pencil.
"After that each of you must write the color (R/B) of your own spot, or 'I do not know', and the other 6 will not see what you wrote.
"The jester will collect all 7 papers, and if I find
* at least one correct answer AND not a single wrong answer, every one of you will be awarded a sack of gold;
* if all answers are 'I do not know' OR there is at least one wrong answer, then I will have to execute all 7 of you as proven frauds.
"So work out your strategy, before the jester enters the room. Best answer for strategy with best odds of success.
Thanks to Phineas Bogg we already know that it is possible to have odds of success at least 3/4 Phineas Bogg is right. The probability to give the right answer for a particular individual is always 1/2. The average number of correct answers is equal to the average number of wrong answers. To maximize the probability to win, we should group wrong answers and separate correct answers. In total there are 2^7=128 combinatons of coloured spots. The optimal strategy presumes WIN for 112 combinations (one person answers correctly while all the others pass) and LOOSE for 16 combinations (everyone answers incorrectly).
The probability to win in the optimal strategy is 7/8. The optimal strategy is constructed below.
Let's numerate wise men and consider combinations of colors as 7-bit words. Bits are either 0 or 1: n-th bit is 0 if n-th wise men has BLUE spot and 1 if he has RED spot. We call two words "neighbors" if their six bits at the same positions coincide and one bit is different. Suppose, we have an optimal strategy. 16 LOOSE combinations (or words) are distributed in such a way, that all their neighbors are WIN combinations. Since each word has seven neighbors, then each of 112 WIN combinations has one and only one LOOSE neighbor. Suppose, the jester marked wise men as (0,1,1,0,1,0,0). Then the first men sees (?,1,1,0,1,0,0), the second men sees (0,?,1,0,1,0,0) etc. Substituting ? by 0 or 1, the wise men reconstruct two possible combinations. If the combination (0,1,1,0,1,0,0) is WIN, then one man reconstructs the (WIN,LOOSE) combinations and six men reconstruct (WIN,WIN) combinations. This happens, because WIN has only one LOOSE neighbor. If the conbination (0,1,1,0,1,0,0) is LOOSE, then all seven men reconstruct (WIN,LOOSE) combinations, because LOOSE have all WIN neighbors.
The optimal strategy is the following. If a wise man reconstructs combinations WIN and LOOSE, he guesses for WIN. If a wise man reconstructs combinations WIN and WIN, he passes. From the above example we see that the WIN and LOOSE combinations correspond to actual wins and looses.
Now, the wise meen need to construct 16 LOOSE combinations. There are words of 7 bits - ABCDEFG, and the task it to specify 16 words such as any two words have at least three distinct bits. These will be the LOOSE combinations. The remaining words cannot have more than one LOOSE neighbor, because this would imply only two distinct letters in LOOSE words. They will also have at least one LOOSE neighbor, because there are 16*7=112 remaining words. As we see, all the requirements for WIN/LOOSE combiniations will be satisfied.
Explicit construction can be made in the same way as in error-correcting codes. First 4 bits - ABCD - are used to write numbers from 0 to 15 in the binary system. The remaining 3 bits - EFG - are parity checks. We can specify them as
E = (A+B+C+D) - B = A+C+D
F = (A+B+C+D) - C = A+B+D
G = (A+B+C+D) - D = A+B+C
Addition rules are parity rules: 0+0=1, 0+1=1, 1+1=0. The bits A,B,C,D in two different words cannot be all the same by construction. If two words have one distinct bit among A,B,C,D, then at least two of the bits B,C,D are the same,
while the combinations (A+B+C+D) are different. In this case, at least two of the three bits EFG are diferent. If two words have two distinct bits among A,B,C,D, then the combinations (A+B+C+D) are the same. Since at least one of the bits B,C,D is different, then at least one of the bits E,F,G will be also different. Thus, the above rules give the desired construction.
For the sake of completeness I give the LOOSE combinations explicitly. First 8 combinations are
0 0 0 0 0 0 0
0 0 0 1 1 1 0
0 0 1 0 1 0 1
0 0 1 1 0 1 1
0 1 0 0 0 1 1
0 1 0 1 1 0 1
0 1 1 0 1 1 0
0 1 1 1 0 0 0
The remaining 8 combinations are obtained by interchanging zeros and ones.
EDIT:
Jack, the strategy is like this.
Each wise man has a number. When a wise man sees spot colors of others, he makes a 7 bit combination. In the bit which has his own number, he puts ?. In the bits with numbers corresponding to other wise men he puts 0 for BLUE and 1 for RED. For example, if men 2,3,7 have BLUE spots, and men 4,5,6 have RED spots, then man 1 makes the combination: ?001110. Then he checks, whether the six visible bits, which he made, coincide with one of the 16 LOOSE combinations described above. In this example, they are the same as in the second LOOSE combination 0001110. Then he votes in such a way, that the LOOSE combination is avoided, i.e. for 1=RED. If the six visible bits do not fit to any of the 16 LOOSE combinations, the wise man says: "I do not know".
Phineas Bogg, one does not need to use the whole Hamming technique. However, it is impossible to avoid using (may be re-inventing without realizing this) a part of it. Since the right answers should be spread, we have exactly the same problem as in the coding theory: write down 16 words using 7 bits in such a way that each two words have at least three different bits. You can reformulate the problem in terms of graph theory or in terms of distances between points, but the essence will remain the same. In one or another way you need to build 16 Hamming code words. Great job, Zo Maar. Very impressive. Wanna meet up in Vegas sometime. Report It
Sorry about the thumbs down. Report It
Edit2:
I found this problem in a puzzle this weekend. I do not think I would have come up with the answer as it has been awhile since I have thought about Hamming Codes or the game of Nim... I will be curious to see if there is an answer that doe snot use this technique.
Edit:
I have been thinking about this, and I believe that the optimal probability of success is at most 7/8 (and probably is 7/8). My reasoning is that for every case where a given person guesses correctly, there is an identical case where he is incorrect, so the best we can hope to do is have one person be right in each of the successes and all 7 be wrong in the failures, this gives a maximum success to fail ratio of 7 : 1 which implies an upper bound of 7/8 on the probability of success....
Old stuff:
Well... I can beat 3/4, but only by a small amount and I would caution anyone thinking about this problem not to read this as I highly doubt this will lead to the optimal solution.
To beat 3/4. The first four people agree that if any of them see three of one color among themselves that they guess the other color. The probability that this happens is 5/8 and the probability that they survive such a guess is 4/5.
The last three people will know whether this is happening as they can see all of the first four colors. So they know if they see two of each among the first four then the first four people will not answer, so it is up to the last three. The last three then decide to answer the opposite of whatever color they see two of. This has a 3/4 chance of success.
So the probability of survival is (5/8)*(4/5) + (3/8)*(3/4) = 25/32. This slightly better than 3/4, but I am almost 100% certain this is not the best answer. |
