Captain Nefarious has captured you and two of your friends, Alice and Bob. Being a villain, he has a natural desire to monologue, so he sits you down (guarded, of course by his Largely Incompetent Henchmen), and explains his Nefarious™ Plan:

"Each of you will be placed in a separate room, which provides no way of communicating with anyone outside the room.

"Each day, my True Random Colour Generator™ will display one of three random colours ($\color{red}{\text{RED}}$, $\color{blue}{\text{BLUE}}$, or $\color{green}{\text{GREEN}}$) on the wall of your room. Then each of you will be given a chance to guess what colour one of your friends was shown.

"You will each tell me the name of one friend (not yourself), and the colour you think they were shown. If none of you name the same friend, and at least one of you names the correct colour, you will live another day. If two of you name the same friend, or if none of you name the correct colour, I will immediately feed all of you to my HeroEater™—my patent-pending new hero disposal device."

Being a True Villain, he is contractually obligated to allow the three of you to talk among yourselves before you are separated. "But no funny stuff," he warns, "or you'll be meeting the HeroEater™ sooner than you'd like."

You, Alice, and Bob quickly put your heads together to think up a strategy. You know that an Elite Extraction Team will be dispatched to rescue you, but you don't know how long it will take. It could be a day, or it could be 20 years.

Is there a strategy that will guarantee your survival until the Elite Extraction Team arrives?

If not, what plan gives you the best probability of surviving until you are rescued (i.e. what strategy maximizes the probability that at least one of you will correctly guess another's colour?)

Disclaimer: I don't know if there is a guaranteed solution to this problem. I have been able to devise a strategy that provides a $>77\%$ (i.e. $\frac79$) chance of survival each day, but there could be something better. (If your solution has a smaller probability, still feel free to post it.)

  • 1
    $\begingroup$ Each person gets a random color, so it could be GGR or BBB or GBR. $\endgroup$ – GentlePurpleRain Dec 18 '15 at 0:12

This is a proof that it is impossible to beat $\frac{7}{9}$.

There are 27 equally likely situations for the choice of colors. Each person will guess correctly in 9 situations. However, for any two people, they will both be correct in 3 situations (three possible colors for A, B has the color A guesses and C has the color B guesses). By inclusion-exclusion, the number of situations in which at least one person is correct is $9+9+9-3-3-3$ plus the number of situations where all three are correct. The maximum of this achieved when all three people are correct whenever any two are, resulting in a value of $9+9+9-3-3-3+3=21$. Therefore, it is not possible to do better than $\frac{21}{27}=\frac{7}{9}$.

  • 1
    $\begingroup$ One intuitive way to think about this is that if the people are arranged linearly, then you show one their color, hear their guess, show the next person their color and so on - and at each step, the chance of success is obviously $\frac{1}3$ since the color was chosen at random after the guess was set. However, if they are in a cycle, this breaks down. (I leave this comment possibly for the benefit of others since it took me a while to see why the case of 3 people being correct could depend on the strategy but the case of 2 people being correct did not). $\endgroup$ – Milo Brandt Dec 18 '15 at 4:56

This solution gives a 7/9 probability of survival.

As JonTheMon has explained, agreeing on a cycle of A $\to$ B $\to$ C $\to$ A is necessary to ensure that the same person won't be chosen twice. This limits some of the strategies that can be chosen.

The team can improve over random color selection, however, by each naming the color that they see. They will succeed as long as at least 2 walls display the same color. That occurs with probability p $= 1 - \frac{2}{3}\cdot\frac{1}{3} = \frac{7}{9} \enspace$.

  • 2
    $\begingroup$ Welcome to PuzzlingBeta. MathJax provides useful formatting tricks for this site. I've edited your answer with a few to help get you started. You can view them by clicking on the "edited [time] ago" link next to your name. In your answer, you might want to explain your calculation since it is often hard to pin down the semantics of numbers in probability calculations. E.g. something along the lines of "complement to having all different colours". Since this relies on heroes hearing each other sequentially and simplifies the name portion, it would also be good to state the assumption. $\endgroup$ – Lawrence Dec 18 '15 at 0:12

8/27 chance of dying each day.

You can avoid the first part of doom by having a circle of guessing: you guess Alice, Alice guesses Bob, Bob guesses you.

The color part is tricky, since your color has no bearing on their colors. To avoid that, all of you guess the same color. That gives $(\frac{2}{3})^3$ chance of dying each day.

  • $\begingroup$ Not bad for a baseline, but there are definitely better strategies. Also, note that all of you guessing the same colour is no different than all of you guessing a random colour, in terms of the probability. $\endgroup$ – GentlePurpleRain Dec 17 '15 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.