1
$\begingroup$

Consider a game played with 12 people. 9 are randomly assigned to Team Good and 3 to Team Evil. Players on Team Evil know their teammates, but players on Team Good don't. Two of the players on Team Good are secretly told that they'll be choosing a button to press during the game. Gameplay proceeds as follows:

  1. All of the players talk publicly with each other.
  2. Everyone goes into separate rooms. The designated button-pressers each receive a red button and a green button, and each chooses one to press. Then the buttons are taken away, and everyone returns to the common area.
  3. The three players on Team Evil reveal themselves, and collectively guess one player who they believe is a button-presser.

Team Good wins if Team Evil's guess was incorrect and the buttons pressed were different colors. Team Evil wins if their guess was correct or the buttons pressed were the same color.

To close a silly loophole, assume that Team Evil has access to an infinitely powerful computer in Step 3, so using cryptography is pointless unless it's information-theoretically secure.

What strategy should Team Good use to maximize their winning chances?

Bonus: Add a 13th person. It's common knowledge that this person is on Team Good and is not a button-presser. Does this increase Team Good's winning chances?

$\endgroup$
16
  • $\begingroup$ Just to clarify, in phase 1 and 2 nobody knows who is who, who is in each team and who has the device? That is, unless they guess it from the talking. $\endgroup$
    – Florian F
    Aug 27 at 8:09
  • $\begingroup$ I assume they cannot concoct a group strategy since they don't know who's on their team so strategies must be worked out on an individual basis? $\endgroup$
    – hexomino
    Aug 27 at 10:48
  • $\begingroup$ @FlorianF For the people on Team Good, that's correct. Team Evil people know each other though. $\endgroup$ Aug 27 at 14:22
  • 1
    $\begingroup$ @JosephSible-ReinstateMonica but there's no way to plan a group strategy without discussing it first whereby Team Evil would have to be included and could undermine the plan. Am I missing something? $\endgroup$
    – hexomino
    Aug 27 at 15:16
  • 4
    $\begingroup$ This question has been changed in a way that makes my answer incorrect. I would appreciate if you can change it back & ask another question with the edits if you so desire. I saw your comment that says my answer was "against the spirit of the puzzle." But what is "the spirit of the puzzle?" No one knows. It is not written down. With all due respect, that comment simply means "I messed up and didn't mean to allow that." It is incredibly frustrating to find solution that works by the written rules and then have it invalidated and downvoted based on unwritten additional rules in someone's head. $\endgroup$
    – Ankit
    Aug 28 at 22:58
5
$\begingroup$

Original problem statement

Consider a game played with 12 people. 9 are randomly assigned to Team Good and 3 to Team Evil. Players on Team Evil know their teammates, but players on Team Good don't. Two of the players on Team Good are secretly assigned devices with red and green buttons on them. Gameplay proceeds as follows:

  1. All of the players talk publicly with each other.
  2. The two players with buttons each secretly choose one to press.
  3. The three players on Team Evil reveal themselves, and collectively guess one player who they believe has a device with buttons.

Team Good wins if Team Evil's guess was incorrect and the buttons pressed were different colors. Team Evil wins if their guess was correct or the buttons pressed were the same color.

What strategy should Team Good use to maximize their winning chances?

Solution

Besides the point but I'd like to point out that the qualifiers "good" and "evil" are arbitrary. In that scenario, "Team Good" could be a group of terrorists trying to detonate a nuclear device in a kindergarten and "Team Evil" could be a group of undercover parents trying to prevent that from happening. So calling the first team "Good" just tells on which side you are. These are just two teams with opposing goals.

Anyway.

The probability of success for Team Good is

6/11 * 7/9 = 14/33 ~= 42%.

Because...

Since the bad guys already know each other, they have two objectives:
1. Find one button holder among the known good guys by detecting any attempt to communicate which button they would press.
2. Prevent coordination between button holders by interfering or mislead them into getting the wrong information.

The button holders would have the following objectives:
1. Provide information for the other button holder regarding what button they will press,
2. Figure out what the other button holder will press.
3. Minimize information revealing they are a button holder.

Now, if the button holders behave differently than the other good guys, that can help the other button holder to decide which button to press. But the bad guys can mimic the behaviour of a button holder. The buton holders don't know who is who, so they can be misled and get the wrong information. The bad guys on the other side won't be mislead and will get reliable information to uncover the button holders. Leaking information about who has the buttons is a small advantage for Team Good but a larger advantage for Team Evil. Therefore Team Good must act in a way that doesn't reveal who has the buttons.

The simplest strategy would be for the button holders to just press a random button and otherwise act like any other good guy. This gives a success rate of 1/2 for pressing different buttons and 7/9 for not being picked by the bad guys who have no clue. This is a success rate of 1/2*7/9 = 7/18 = 38.88% overall.

But a better strategy is to split the players randomly in two groups of 6, one being instructed to press the red button, the other to press the green button. This way, the probability of the two button holders being in different groups, and therefore pressing different colors, is 6/11, slightly better than 1/2. And the bad guys are not the wiser. The success rate for Team Good becomes 6/11 * 7/9 = 14/33 = 42.42%.

It is important that it is not a bad guy who forms the red and gree groups, because if he puts all good guys in the same team, the probability to press a different color drops to 1/2. So it must be done in a way everybody is confident that the assignment has been done impartially.

I don't know if that is optimal, but it is the best I can come up with. And 42% always looks like a good answer.

Objections and correction.

A valid objection by JS1 is that Team Evil can do better than just pick one of the 9 Team Good members. Team Evil only needs to find a button holder when the button holders succeed in pressing different buttons. That means that Team Evil can assume there is one button holder in each color group when it matters. With that knowledge it is better to pick one good guy from the smaller color group. They can uncover a button holder with probability 1/3 or 1/4 depending on the distribution (3+6 or 4+5).

The overall probability to uncover a button holder is tricky. You have to figure the probability of each distribution to happen, given that they succeeded in pressing different buttons, then apply the rate above.

I am not sure how to compute that properly. I ran a computer simulation and found the same success rate of 40.15% as JS1 and Retudin. That should be the correct answer.

Retudin wonders whether Team Evil can bias the choice of colors towards 3/0 for Team Evil. I think that if colors are chosen randomly by picking marbles from a hat Team Evil cannot introduce a bias. Whoever objects that method only reveals himself to be evil. The remaining players can then split between red and green producing on average a more equal split.

$\endgroup$
8
  • $\begingroup$ This is the only answer so far that solves the spirit of the problem instead of exploiting silly loopholes. I'm not 100% sure if this is optimal either, but I'll give you the check mark for this in a day or two if nobody beats it by then. $\endgroup$ Aug 28 at 21:31
  • 2
    $\begingroup$ Although your proposed strategy does beat the naive strategy, it doesn't have a 42.42% success rate. What's wrong is that you don't account for the fact that the evil team knows each other and do better than pick a random good team member as a button holder. For example, given a random division into two groups of six, all 3 evil team members will end up on the same side 2/11 of the time. When this happens, the evil team should pick one of the 3 good team members in that same group, which will hit on a button holder 1/3 of the time rather than 2/9, when diff buttons are pressed. $\endgroup$
    – JS1
    Aug 29 at 4:29
  • $\begingroup$ In the case where the evil team is split 2/1, they should pick one of the 4 good team members in the group with 2 evils. By my calculation, this leads to a final success rate of this: (2/1 evil split case) 9/11 * 20/36 * 3/4 + (3/0 evil split case) 2/11 * 18/36 * 2/3 = 53/132 = 40.15% $\endgroup$
    – JS1
    Aug 29 at 4:33
  • $\begingroup$ Yes this answer should be 40.15%, assuming the division in groups can be done without team evil somehow influencing the partition in favor of the 3/0 evil split (which does not seem obvious to me) $\endgroup$
    – Retudin
    Aug 29 at 7:25
  • $\begingroup$ Yes, you are right. I updated the answer accordingly. $\endgroup$
    – Florian F
    Aug 29 at 8:37
1
$\begingroup$

100% success rate with (yeah, I know, I'm stupid that way, sorry):

"We outnumber you three to one. You'd better guess intentionally wrong, OR ELSE. Now, would the button pressers please choose their colours out loud."

58% success rate by an actual strategy that doesn't require prior planning:

"Let's randomly choose one of us to be the trusted one. There's a 75% chance it will be one of the good guys. Then everybody will walk past the trusted guy, and may choose to reveal their button to the trusted guy but no-one else."

Then

Repeat these revealing rounds until a round occurs when exactly one of the button carriers revealed the button, which the trusted guy announces. Then the one that revealed their button will choose green, and the other will choose red.

Since there's still a 2 in 9 chance that the bad guys guess right purely by chance, the probability of success goes down a bit.

$\endgroup$
6
  • 2
    $\begingroup$ Hey! I believe no secret communication is allowed in the problem, as per comments under OP $\endgroup$ Aug 27 at 16:22
  • 1
    $\begingroup$ lmao i like the first solution. As for your actual solution, I don't think that meets the criteria of the "all players talk publically" $\endgroup$
    – Ankit
    Aug 27 at 16:24
  • $\begingroup$ I assume the secret communication rule can be circumvented by publicly making encrypted statements that only the trusted one can decode. $\endgroup$ Aug 27 at 16:35
  • $\begingroup$ Well, I'm not sure how to encrypt the physical act of showing the button (because saying you have a button can easily be faked). :-) I'm not sure if allowing a person to peek into your pocket falls outside the scope of the puzzle. If it does, I'm sure OP will correct me. (..and the puzzle itself. The comment section isn't usually considered required reading when solving puzzles here.) $\endgroup$
    – Bass
    Aug 27 at 16:48
  • $\begingroup$ @GoblinGuide I did something somewhat similar in my answer. $\endgroup$
    – Ankit
    Aug 27 at 17:27
1
$\begingroup$

This question has been changed in a way that invalidates my answer.

Previously, the button-pressers had their remotes from the start, and all communication was allowed as long as it was done "publicly." In this question's original state, my answer was perfectly valid, and probably the correct answer. Please feel free to check the edit history to confirm.

Probability of Success:

$\frac{7}{9}$ or $77.7777...$%

As pointed out by @NuclearHoagie in the comments

There is technically a non-zero probability that someone will randomly guess a detail exactly and be talking to a button presser, but the chances of this occurring is the lower than you and a friend randomly picking points on a number line and picking the same number. In other words it is statistically insignificant and can be called 0, as the chances of it occuring is $\frac{1}{\infty}$

Intro to relevant maths:

My solution requires use of the Diffie-Hellman Protocol which is esentially creating a numerical key based on two secret keys.
Lets say A & B want to create a DHP key, and C is eavesdropping-- that is C can see/hear everything communicated between A & B.
A & B start by deciding on agreeing on two numbers, $p$ & $q$, which will be relatively prime. C will also be in on this info. For sake of explanation lets say $p=113$ and $q=109$. Now A and B will both think of their own secret numbers, $a$ & $b$, for the explanation lets say 3 and 5. A doesn't know $b$, B doesn't know $a$, C knows neither.
A calculates $c = p^{a}\mod q$ and shouts what $c$ is (in this case 64). B calculates $d = p^{b}\mod q$ and shouts what $d$ is (in this case 43). Now A calculates $k = d^{a}\mod q$ and B calculates $k = c^{b}\mod q$. They will get the same answer, which is k (in our case 46). The reason they get the same answer is that $k = c^{b}\mod q = (p^{a}\mod q)^{b}\mod q = (p^a)^b \mod q = p^{ab} \mod q$. Doing the same with A's math will yield $p^{ba} \mod q$ which of course is equivalent. C cannot calculate either as C doesn't know either A or B and would have to do guess and check based on the values c and d.
The DHP key (k) can now be put in to base 26 and used to generate a keyword for a keyword cipher. For 46 this would be 1,20 which creates the keyword "at". Messages can be shouted out loud using this code and C will have no idea what's being said. I used small numbers in this example but using bigger numbers can keep th much bigger k values which is not that much harder for A & B to deal with, but exponentially harder for C.

If you do not understand what I have written, there's a great Zach Star video explaining the same.

Strategy:

Step 1:

Each person is assigned 2 different aspects of the device to comment on (they don't say it yet). For example, weight of device, texture of device, texture of buttons, material of device, material of buttons, height/width/length of device, h/w/l of each button, red/green/blue/alpha values of device, r/g/b/a value of green button or red button, etc.

Step 2:

Each person establishes 1 DHP key with every other person in the room. That means that even though they are shouting out things to all 12 people (meeting the communicating publically requirement), only 2 people are understanding the communication at a time.

Step 3:

Each pair goes 1 at a time in a predetermined order. The first person uses the first DHP key to give their assigned details about the remote with the buttons. The second person uses gives their assigned details. They then agree on one person pushing green and the other pushing red. Of course in all but 1 conversations, at least 1 side is making things up. But when the 2 people with remotes talk, they will be able to easily verify what is being said to them.

Step 4:

As agreed upon in the rounds of discussion, the two button pressers press the colors. The Evils have no idea who pressed the buttons. They have to guess by chance giving them a 2/7 chance of winning.

Proof of optimality

It is not physically possible to get odds above 7 in 9, as regardless what you do, the Evils can just decide to take a random guess.

It is further not possible to not have the $\frac{1}{\infty}$ subtracted, because information is being exchanged and people are making up that information and there is always a technical, non-zero yet statistically insignificant, chance that someone will get the right guess.

This was a really fun puzzle. Thank you!!

$\endgroup$
11
  • $\begingroup$ Good answer, but this requires that both button devices are identical, which is not a given. It won't be possible to distinguish between someone who's accurately describing a button device that's different from yours and someone who's just pretending to have one. Even if the devices are identical, there is non-zero probability that someone happens to describe it correctly by chance alone (or by just repeating others' statements). $\endgroup$ Aug 27 at 17:38
  • $\begingroup$ Since the button pressers don't know if they are talking to each other, buttonless good guys or even the baddies, any detail given in this manner can be reused, and the baddies can relay any given details to each other. Also, the bad guys can fake having a button in order to determine who doesn't. $\endgroup$
    – Bass
    Aug 27 at 17:38
  • $\begingroup$ @Bass So with this workaround are you accepting secret communications between two players? Edit: nvm you aren't OP hahaha my bad. $\endgroup$ Aug 27 at 17:43
  • $\begingroup$ @NuclearHoagie The problem gives no reason to suggest they are not identical. As for your "non-zero probability" I mean yes you are correct and I will put an edit regarding that but that non-zero is statistically insignificant, because one person can just ask for another decimal place, until they are satisfied. $\endgroup$
    – Ankit
    Aug 27 at 17:50
  • $\begingroup$ @Bass Even if the evils transfer details to each other, it wouldn't help, as the two people are suppsed to give different details, not say the same thing back to each other. This is written in my answer, but I will put an edit clarifying. $\endgroup$
    – Ankit
    Aug 27 at 17:54
0
$\begingroup$

This is a wrong solution because I misread the problem statement. I thought Team Evil had to guess BOTH device holders, not just one.

Nevertheless, posting it since I spent some time on it, and maybe some of the ideas give some inspiration! :D

Note: even with the misreading, it wasn't a full solution anyway, was just going to post it as some ideas.

Strategy Alpha, the "simple" strategy:

First let's establish the "simple" strategy, which I'm calling strategy Alpha. In this one, no communication happens and both device holders press a random button. We can use this strategy as a baseline to compare more advanced ones against.

Team Good's win chances using Strategy Alpha:

  • P(different buttons were pressed) = 1 - P(same buttons were pressed) = 1 - (0.5) = 0.5 = 50% = 1/2

  • P(Team Evil randomly guesses the two device holders correctly) = 1/9 * 1/8 = 1/72

  • --> P(Team Evil doesn't guess correctly) = 1 - 1/72 = 71/72

  • --> P(Team Good wins) = P(different buttons were pressed) * P(Team Evil doesn't guess correctly) = 1/2 * 71/72 = 71/144 = ~49.31%

Strategy Beta, a more advanced strategy:

First, let's assume Team Evil are just observers, meaning they cannot take part in the conversation. Then, we could do this:

  • Each player is assigned a number (1 to 9) -- (there are 9 Team Good players).

  • All the players count seconds together out loud. 1, 2, 3, ...

  • If you are a device holder, you wait until the count reaches 10*YOUR_NUMBER before revealing yourself. (10 is just a nice round number which gives a good amount of space between potential reveals, to avoid 2 device holders from accidentally revealing themselves if for instance one was too late to reveal themselves and the next player was also a device holder.)
  • Once a device holder revealed themselves, they declare they will press Red and we stop the count.

  • The other device holder secretly presses Green.

  • The observing Team Evil has a 1 in 8 chance to win (1 of the 9 players is a known device holder, so they guess the other one randomly from the remaining 8 players).

  • So with this constraint, P(Team Good wins) = 1 - 1/8 = 7/8 = 87.5%, which is much better than strategy Alpha.

However,

In our problem, if strategy Beta is used, then Team Evil can increase their chances of winning if one of them identifies themselves as a device holder. I say "increase", because it's still not a guaranteed win for Team Evil:

  • Scenario A. If the device holder with the lower player number (between the two device holders) has a lower number than all Team Evil players, then we have the above scenario where Team Evil were just observers -- so Team Evil has a 1 in 8 chance to win.

  • (Note that in the above algorithm, once someone identified themselves as a device holder, only Team Evil players would subsequently identify themselves as a device holder and would be ignored. Similarly if someone speaks up out of order, they would be ignored.)


  • Scenario B. If there is at least 1 Team Evil player with a lower player number than both Team Good device holders, then Team Evil has a 100% chance to win (because both of the real device holders will press the opposite color, meaning they will both press the same color).

I'm not great at probabilities, so not sure how to calculate the probabilities to compare with the "simple" strategy.

  • P(at least 1 Team Evil player has a lower player number than both of the 2 Team Good device holders)

  • = 1 - P(None of the 3 Team Evil players have a lower player number than either of the 2 Team Good device holders)

  • ...?

$\endgroup$
0

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.