5
$\begingroup$

Every participant of a tournament plays with every other participant exactly once. No game is a draw and so, each game had a winner. After the tournament, every player listed the names of all the players, he/she defeated as well as the names of all the players defeated by the players defeated by him/her. For instance, if $A$ defeats $B$ and $B$ defeats $C,$ then in the list of $A$ both $B$ and $C$ are included. Prove that at least one player listed the names of all other players.

$\endgroup$
0

5 Answers 5

5
$\begingroup$

Let's use induction on the number of participants.

If there is exactly one participant, the situation is pretty clear. So suppose that there are $n \geq 2$ participants, and that we have solved the problem for $n-1$ participants.

Let us consider a participant $v$, and take a look at the remaining participants. Among them, we can select a "winner" $w$ such that for each participant (apart from $v$) either he was beaten by $w$, or he was beaten by someone who was beaten by $w$. Let $A$ denote the set of those who were defeated by $w$, and let $B$ denote the rest, so that we know that everyone in $B$ was beaten by someone in $A$.

Now, consider the results of games that $v$ played. If he lost to $w$, then we are done - the choice of $w$ still "works". Similarly, if $v$ lost to someone in $A$, then we are done - $w$ still works. Thus, we can assume that $v$ won with $w$ and with everyone in $A$.

But now $v$ has everyone on his list:

  • $w$ is there, because $v$ won against $w$;
  • everyone in $A$ is there for the same reason;
  • everyone in $B$ is there, because everyone in $B$ lost to someone in $A$, and $v$ won with everyone in $A$.

Thus, in this case $v$ can be chosen, because for each player $v$ either won against him (for $w$ and $B$), or $v$ won against someone who won against him (for $B$). Hence, and we are done.

$\endgroup$
1
$\begingroup$

We will prove this problem by using induction.

  • For $n=2$ it is pretty obvious that this is true - no matter what the outcome of the only match is there always would be a player which has the other player in his list.
  • Suppose that the statement is true for $n-1$. So there would be a player $P_i$ which satisfies the condition, i.e. if $B_{d}(P_i)$ is the set of all player beaten directly by player $P_i$ and $B_{nd}(P_i)$ is the set of all players beaten by a player beaten by $P_0$ (but not directly beaten by $P_i$) then $B_n(P_i) \cap B_{nd}(P_i) = \emptyset$ and $B_n(P_i) \cup B_{nd}(P_i) =$$ \{P_1, P_2, \dots, P_{n-1}\}\setminus {P_i}$. Lets consider another player and suppose that this new $P_n$ is not on the list of $P_i$ (otherwise $P_i$ would be the person we are looking for). This means that $P_n \not \in B_n(P_i) \rightarrow P_i \in B_n(P_n)$ and $P_n \not \in B_{nd}(P_i) \rightarrow (\forall P_j \in B_n(P_i))(P_j \in B_n(P_n)) \rightarrow $$(\forall P_j \in B_{nd}(P_i))(P_j \in B_{nd}(P_n))$. So we see that $P_n$ would have every other player in his list. $\blacksquare$
$\endgroup$
1
$\begingroup$

An approach without graph theory/induction. Here it is, I will use proof by contradiction:

Let the players be $P_1,P_2,...,P_n.$ We consider, $P_1$ to be the player, who won the most number of matches. We partition, the list written by the player $P_1$ into two parts $A$ and $B$, where, $A$ contains the list of players defeated by $P_1$ and $B$ contains the list of players who are defeated by the players in $A.$

We claim, $|A|+|B|<n-1.$

This means, there exists a player ,call it $P_i$ who is not in the list of $P_1.$ This means, the list of $P_i$ contains $P_1$. We again partition, the list made by $P_i$ as $A_i$ and $B_i $ (analogous to the previous way of partitioning). The set $A_i$ contains the list of players, defeated by $P_i$ and this includes $P_1$ and $B_i$ contains the set $A.$

We note, that if there were any name, in $A$ that had defeated $P_i$ then $P_i$ would be there in $B,$ and so, $P_i$ would be in the list of $P_1,$ but, this is not the case as we formerly assumed, that $P_i$ is not in the list of $P_1$. So, this means, $P_i$ defeated all the players in $A$ and so, this means, $P_i$ has the names of $P_1$ and all the names in $A$ and all the names in $B,$ i.e $A\cup B\cup P_1\subset A_i\cup B_i,$ which implies, $P_i$ has more number of names, than $P_1,$ and this is a contradiction as well, for we assumed that $P_1$ has the highest number of names in her list. Therefore, our claim must be wrong that $|A|+|B|\lt n-1.$ Thus, $P_i\in A\cup B,$ and hence $P_1's$ list contains name of all other players.

$\endgroup$
0
$\begingroup$

Let $L$ be a maximal totally ordered subtournament, i.e., $L = \{P_1, \dots, P_k\}$ where $P_i$ lost to $P_j$ for all $i < j$. By maximality, every player not in $L$ lost to some player in $L$ (for otherwise we could call that player $P_{k+1}$). Therefore the player $P_k$ has the required property.

(This proof is really the same as Jakub's inductive proof, just phrased differently.)

$\endgroup$
0
$\begingroup$

Let Max be a player with the maximum number of wins (possibly tied with others). If some other player beat Max, and also beat everyone that Max beat, then that player would have more wins thasn Max. Therefore, every player other than Max was either beaten by Max or beaten by someone that Max beat.

$\endgroup$

You must log in to answer this question.

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