1
$\begingroup$

In a tournament every player competes against each other. Every match has a winner.

A tournament has property $P_k$ if for every set $S$ of $k$ players there exists a player $a\notin S$ who beats every players $b\in S$ . Show that if $$\binom{n}{k}\left(1 - 2^{-k}\right)^{n-k} < 1$$ then there exists a tournament with $n$ players that has the property $P_k$.

$\endgroup$

1 Answer 1

5
$\begingroup$

For conciseness, let's say a group is beaten by a player if the player beats all players in the group. Choose the winner in each game independently with equal probabilities $1/2$. The probability of a group of $k$ players not being beaten by a given other player is $1-2^{-k}$, and since the results are all independent the probability of the group not being beaten by any of the other $n-k$ players is $(1-2^{-k})^{n-k}$. There are $\binom nk$ different groups of $k$ players, so the expected number of groups beaten by no player is the left-hand side of your inequality. If this is less than $1$, it follows that there must exist at least one tournament for which the number of such groups is zero, and this tournament has property $P_k$.

$\endgroup$

You must log in to answer this question.

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