1
$\begingroup$

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!

$\endgroup$
1
  • 1
    $\begingroup$ You've referenced a probability function, which is a good idea. Have you checked what that probability function says in the case with 5 dice? $\endgroup$ Commented Apr 18, 2021 at 15:49

3 Answers 3

2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Excuse me, your computation seems correct, but I asked about all players to be impostor at least once, not just one of them. Assuming independence, as Ross suggested, one has to raise $(1-P_n)^{15}$, and you reach the same result as him. $\endgroup$ Commented Aug 28, 2022 at 17:27
  • 1
    $\begingroup$ It's true. I missed the fact that it needs to be for all players. But $n>13$ gives a lower bound. And to approximate the real answer, you could consider $\left(1-\left(4/5\right)^n\right)^{15} > 0.95$, which gives $n>25$. But I'm trying to figure out an exact solution. Very interesting problem! $\endgroup$
    – ordptt
    Commented Aug 28, 2022 at 17:35
  • 1
    $\begingroup$ If you are interested in the results of a numerical simulation, I simulated 1,000,000 games for 25 and 26 rounds each, resulting in probabilities of 0.943845 and 0.955587 respectively, which shows that the approximation gave the right result. If you do a linear interpolation, you get that the probability is 0.95 for n=25.524, which is really close to 25.454 from the approximation. $\endgroup$
    – ordptt
    Commented Aug 28, 2022 at 17:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .