Probability game - everyone to be impostor (Among us)

Question

Problem. Suppose we have a game with $15$ players, which consists of $n\geq 5$ rounds. In each round, $3$ of them are selected in a random fashion and will have the role of impostor. What is the minimum value of $n$, such that it is very possible that every single player will be an impostor at least for a round? (,,very possible'' means probability of $95\%$)

My attempt: We label the players by numbers from $1$ to $15$. A round can be modelled by a subset $\{a,b,c\}\subseteq \overline{1,15}$, in this way we specify the $3$ impostors. For a fixed round, the random selection of impostors is equivalent to the random selection of a subset $A$ with $3$ elements from the set $\overline{1,15}$. There are $\binom{15}{3}=455$ such subsets.

Denote the selected subsets by $A_1,...,A_n$. By playing $n$ rounds, we have a total of $455^n$ possibilities for those $n$ subsets. A favourable situation occurs if and only if $A_1\cup...\cup A_n=\overline{1,15}$. Denote by $f(n)$ the number of these situations. Now, the probability is $P(n)=f(n)/455^n$, and we want to compare it with $0.95$.

QUESTION: How to compute $f(n), n\geq 5$? It may be a recursive formula, involving changes of $m=15$, but I failed to find such one.

Thank you for your time and effort!

Answer 1

As ordptt wrote, the probability of a single player not being chosen in $n$ rounds is $(4/5)^n$. Similarly, the probability that a given set of $k$ players, $1 \le k \le 12$, all escape being chosen is $$p(k,n) = \displaystyle \left({15-k \choose 3}/{15 \choose 3}\right)^n$$ By the inclusion-exclusion principle, the probability that nobody escapes is $$ 1 - {15 \choose 1} p(1,n) + {15 \choose 2} p(2,n) - {15 \choose 3} p(3,n) + \ldots - {15 \choose 12} p(12,n) $$ i.e. $$ 1-15 \left(\frac{4}{5}\right)^{n}+105 \left(\frac{22}{35}\right)^{n}-455 \left(\frac{44}{91}\right)^{n}+1365 \left(\frac{33}{91}\right)^{n}-3003 \left(\frac{24}{91}\right)^{n}+5005 \left(\frac{12}{65}\right)^{n}-6435 \left(\frac{8}{65}\right)^{n}+6435 \left(\frac{1}{13}\right)^{n}-5005 \left(\frac{4}{91}\right)^{n}+3003 \left(\frac{2}{91}\right)^{n}-1365 \left(\frac{4}{455}\right)^{n}+455 \left(\frac{1}{455}\right)^{n} $$

The first $n$ for which this $> 0.95$ is $26$.

Answer 2

One simple approach is to assume the fact of players not being chosen is independent. It is not correct, but it gives a good feeling. After $n$ rounds the chance a given player has not been chosen is $0.8^n$ and the chance the player has been chosen is $1-0.8^n$. This is correct. We now use independence to say the chance all the players have been chosen is $(1-0.8^n)^{15}$. In fact knowing one player has been chosen reduces the chance another has, but when you are looking for high chance that all have been chosen the impact should not be too large. Then for any given probability $p$ you want that all are chosen $$p=(1-0.8^n)^{15}\\ p^{1/15}=1-0.8^n\\ 1-p^{1/15}=0.8^n\\ n=\frac{\log(1-p^{1/15})}{\log 0.8}$$

Answer 3

The probability, $P_1$, of a player not being an impostor in a single round is given by $$P_1=\frac{14}{15}\frac{13}{14}\frac{12}{13}=\frac{4}{5}$$ You can also see this by taking the ratio of the number of subsets that contain the player to the number of all subsets: $$P_1=\binom{14}{3}/\binom{15}{3}=364/455=4/5$$

Since rounds are independent, the probability that a given player will not be the impostor for $n$ games, $P_n$, is $$P_n=\left(\frac{4}{5} \right)^n$$ Therefore, the probability that a player will be impostor at least once in $n$ rounds is simply $1-P_n$. To satisfy the "very possible" condition, then $$1-\left(\frac{4}{5} \right)^n>0.95$$ $$n>13$$