Secretly press different buttons

Question

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?

Answer 1

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.

Answer 2

100% success rate with lateral-thinking (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.

Answer 3

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!!

Answer 4

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)


• ...?