5
$\begingroup$

This puzzle is based on Among Us; however, knowledge of the game is not required for this puzzle.


10 dummies are on a spaceship, in which there are 3 impostors and 7 crewmates.

For the sake of simplicity, let's assume that the dummies will do nothing but calling Emergency Meetings one after another. In each Emergency Meeting, they vote to get one random dummy ejected from the spaceship. Each impostor and crewmate has an equal chance of being chosen. Ejected dummies no longer participate in future Emergency Meetings.

Impostors win if the number of impostors remaining on the spaceship is equal to the number of crewmates remaining (i.e. 3 impostors vs 3 crewmates, 2 impostors vs 2 crewmates, or 1 impostor vs 1 crewmate).

Crewmates win if all impostors are ejected from the spaceship.

When either side reaches their goal, the game ends.

What are the possibilities of winning for impostors and crewmates, respectively?

Among Us (This image is a screenshot of Among Us that has nothing to do with the puzzle itself.)

Moreover, does a general formula for calculating the possibilities of winning for impostors and crewmates exist, if there are $D$ dummies in total, and $I$ impostors among them? $(2I<D)$

$\endgroup$
5
  • 8
    $\begingroup$ This looks like more of a math problem than a puzzle. It seems to me that it could be answered with basic combinatorics. $\endgroup$
    – Deusovi
    Oct 4 '20 at 3:06
  • $\begingroup$ @Deusovi I'm sorry for the mistake, this is my first question here... and it probably can be answered with combinatorics, but I'm not good at it so I wrote a computer program to solve it instead... $\endgroup$
    – birdue
    Oct 4 '20 at 3:29
  • $\begingroup$ This is a cool game! $\endgroup$ Oct 4 '20 at 13:44
  • $\begingroup$ I don't understand the purpose of the vote. Why not just have an automated mechanism expel one person at random every so often? $\endgroup$
    – msh210
    Oct 4 '20 at 22:41
  • 1
    $\begingroup$ @msh210 Because in the actual game played by real players, people will discuss who is the most likely to be an impostor in emergency meetings and vote them, instead of voting randomly! This can't be manifested in a math question though, so I changed the it to voting off someone random while keeping the term emergency meeting in the game. $\endgroup$
    – birdue
    Oct 5 '20 at 1:22
8
$\begingroup$

The answer follows from Bertrand's Ballot Theorem:

To simplify, assume we continue ejecting dummies until none remain, and impostors still win if they match the crewmates in number at any point before the final ejection. This doesn't change the result.

Then, tally the dummies in reverse order of ejection. We want to know how likely it is that the number of crewmates is greater than the number of impostors after every step. This probability, that the crewmates win, is given by Bertrand's Ballot Theorem. With $p$ crewmates and $q$ impostors, assuming $p>$q, the probability is $$\frac{p-q}{p+q}=\frac{4}{10}$$

$\endgroup$
0
$\begingroup$

I am going to use the terms Crew (C) and Imposters (I) for all of my terminology because there are 10 dummies on board, not 7 dummies and 3 imposters. To help organize my thoughts, I put everything in a tree structure.

Below, I have a binary tree of wins and losses. Every left branch is an Imposter being voted out, and every right branch is a Crewmate being vote out. Each node in the tree is organized as (I, C). We reach a leaf node when I=0 or I=C. Green leaf nodes means Crew wins and red means Imposter wins. I didn't create a full tree because I realized that the tree has repeated branches (ex: the node (1,5) is repeated once to the left of (2,6), once to the left of (2,5), twice to the left of (3,6), and once to the left of (3,5)). So I only left the unique nodes and counted wins/loses from previously existing nodes. (ex: to the left of (2,6) you look at node (1, 6) and count all of the wins and losses below it.) enter image description here

Adding everything up

under (1,7) we have 6 wins and 1 loss
to the right of (2,7) we have 15 wins and 6 losses
to the right of (3,7) we have 27 wins and 13 losses
Totaling 48 wins and 20 losses. That means there is a probability of 29.41% of Imposters winning, and a 70.59% chance of Crew winning.

Generalization:

For I = 1, it is obvious that the probability of Crew winning is C / (C + I)
For I = 2, to calculate the wins and losses are the equations below, and then to calculate Crew winning you do wins / (wins +losses)
enter image description here
For I = 3, the wins and losses become more complex, and I can't get closer to a "general solution".

I have a feeling that this could be solved some way with the Binomial Coefficient but it has been so long since I have used it that I kept getting wrong answers.

Side node: playing with the tree made me think of the Fibonacci Sequence and makes me wonder if there is no general solution. That you have to manually calculate the wins/losses to get a solution.

$\endgroup$
3
  • 1
    $\begingroup$ Not all of the endpoints are equally probable, so this doesn't work. $\endgroup$
    – Deusovi
    Jul 28 at 20:30
  • $\begingroup$ dang it, I forgot to account for every branch having a 50% chance of happening in my final answer. $\endgroup$
    – rhavelka
    Jul 28 at 21:05
  • 4
    $\begingroup$ But that's also not true. It's a random person that is chosen, not a random role. If there are 6 crewmates and 2 impostors, there's a 75% chance that a crewmate will be chosen. $\endgroup$
    – Deusovi
    Jul 28 at 21:18
-2
$\begingroup$

This problem need two clarifications:

  1. Who knows who are the impostors? Some viable options:
    a) none of them knows who are the impostors
    b) impostors know other impostors
  2. How many votes are needed for eject? Some viable options and examples for 4 voters:
    a) 'half' - at least half of the votes are enough, so 2v2 is enough to eject.
    b) 'majority' - more than half of the votes needed, so 2v2 is NOT enough but 3v1 is.

Interestingly, the second clarification is not needed for the '1a' case - when none know who the impostors are, they all randomly vote and cases when a person is not ejected are simply discarded. It turns out that probability for impostors to win in the '1a' case is pwi= 2*I/N = 60% (when N=10 total players, out of which I=3 impostors). Results for different number of impostors in the '1a' case:

  • pwi(10,5)~ 100%
  • pwi(10,4)~ 80%
  • pwi(10,3)~ 60%
  • pwi(10,2)~ 40%
  • pwi(10,1)~ 20%

But the '1b' option is closer to an actual "Among Us" game, where impostors know each other and will always try to help other impostors, while crew members do not know who the impostors are. Therefore, under this option, it is logical that crew members will randomly vote while impostors would either all vote 'yes' to eject if the vote is for a crew member, or all vote 'no' against ejection if the vote is for another impostor. In this case, clarifying if majority or half votes eject does influence the result. I do not have a formula for this case, but I do have a recursive solution. Result numbers for 10 players (7 crew and 3 impostors) are pwi~ 89% (for 2b=half) or pwi~ 95% (for 2a=majority). If we use pwi(N,I,majority) to note the condition, then some results for '1b' are:

  • pwi(10,5, majority)~ 100%
  • pwi(10,4, majority)~ 99.7%
  • pwi(10,3, majority)~ 95.1%
  • pwi(10,2, majority)~ 73.2%
  • pwi(10,1, majority)~ 33.7%

  • pwi(10,5, half)~ 100%
  • pwi(10,4, half)~ 98.8%
  • pwi(10,3, half)~ 88.9%
  • pwi(10,2, half)~ 63.0%
  • pwi(10,1, half)~ 28.8%

As expected, when impostors know other impostors and vote to help them, the chance for an impostor win are significantly higher (and even higher when majority votes are needed for eject).

Note: "everyone has an equal chance of being chosen" (which is stated in problem, and is similar to what happens in real Among Us) is not same as "the group collectively votes at random" (which is not stated in problem, and does not happen in real Among Us, where impostors know each other).

$\endgroup$
5
  • $\begingroup$ The question directly states that everyone has an equal chance of being chosen: the group collectively votes at random. $\endgroup$
    – Deusovi
    Jul 29 at 20:48
  • 1
    $\begingroup$ @lost You seem to have created two different accounts; that makes it harder to edit your own posts (the edits need to be approved by others) as well as responding to feedback. Please check out this page to see how to merge your accounts together. Thanks! $\endgroup$ Jul 29 at 21:37
  • $\begingroup$ @lost, the reason you can't comment on your post is because you're using a different account which doesn't own the post. Please follow the instructions in Rand's comment to merge your accounts together. $\endgroup$
    – bobble
    Jul 30 at 16:16
  • $\begingroup$ @bobble Thanks, I did that - problem was that one post was done as 'guest', because I registered previously on another browser. $\endgroup$
    – lost
    Jul 31 at 8:54
  • $\begingroup$ @Deusovi sorry, I could not comment previously - so I edited in notes. Basically, you have valid point that "the group collectively votes at random" is one thing that can be assumed from question. But another valid assumption is that impostors know each other ( due to "Among Us" reference ). Both are equally valid assumptions (since question does not specify which one to use), and I gave solution values for both of those. $\endgroup$
    – lost
    Jul 31 at 8:58

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