There is a best performer in a round robin tournament

Question

At a social bridge party every couple plays every other couple exactly once. Assume there are no ties. If $n$ couples participate, prove that there's best couple in the following sense: A couple $u$ is best if for every couple $v$, $u$ beats $v$ or $u$ beats a couple that beats $v$.

What I tried:

If $u$ beats some $v$, the base holds.

Suppose $u$ beats $k$ different $v$'s. Then if $u$ beats $(k + 1)$st $v$, we are done. Suppose $u$ loses to $(k + 1)$st $v$, then if one of the $k$ $v$'s beats $k + 1st$ $v$, we are done. Suppose that doesn't happen. Then $(k + 1)$st $v$ will have beaten $k$ $v$'s by transitivity since $(k + 1)$st $v$ beats $u$, $k + 1$ in total. This shows the existence of best couple.

Can you check my work, please?

Answer 1

This argument does not work. You may not assume that $u$ beats $k$ different $v$'s. All you may assume is that for $k$ different $v$'s, either $u$ beats directly or "transitively". Unfortunately when the $k+1$st $v$ comes along, the transitivity is now two steps long and not one step, so the induction breaks down.

Here's a solution, which has some of the same flavor as the original attempt. Write $xBy$ to denote $x$ beats $y$ directly. Since each couple plays every other couple, exactly one of $xBy$ or $yBx$ must hold. For every couple $x$, define $X'=\{y:xBy\}$ and $X''=\{z:\exists y\in X', yBz\}$. Define $f(x)=|X'\cup X''|$. Note that $\{x\}, X'\cup X''$ are disjoint, and we are trying to prove that there is some couple $x$ such that $f(x)=n-1$.

Okay, let $u$ be chosen so that $f(u)$ is maximal. If $f(u)=n-1$, we are done; otherwise choose any $v\notin \{u\}\cup U'\cup U''$. Our strategy is to prove $f(v)>f(u)$.

Lemma 1: $U'\subseteq V'$. Proof: If $t\in U'\setminus V'$, then $uBt$ and $tBv$, which contradicts $v\notin U''$.

Lemma 2: $U''\subseteq V''$. Proof: If $t\in U''$, then there is some $s\in U'$ and $sBt$. But by Lemma 1, $s\in V'$, so in fact $t\in V''$.

Note also that $u\in V'$, but $u\notin U'\cup U''$. Hence $$f(v)=|V'\cup V''|\ge |\{u\}|+|U'\cup U''|=1+f(u)$$ But now $f(v)>f(u)$, which contradicts the maximality of $f(u)$.

Answer 2

Here is another solution, by induction.

Assume that the statement holds for $n-1$. Take a set $T$ of $n$ pairs and arrange a tournament. For each $v\in T$, take one of the best performers in $T\setminus\{v\}$ and denote it by $\sigma(v)$. It is obvious that if $\sigma(v_1) = \sigma(v_2) = w$ for some $v_1\neq v_2$, then $w$ is the best performer in $T$ too. Therefore, $\sigma$ is a permutation of $T$.

Now assume that $\sigma(v)\not> v$ for all $v\in T$. Now denote by $b(v)$ the number of pairs beaten by $v$. Then it follows from the last observation that $b(v) = b(\sigma(v))$: all pairs beaten by $\sigma(v)$ must be beaten by $v$ and $\sigma(v)$ is beaten by $v$). Therefore, $$ \sum_{v\in T} b(v) > \sum_{v\in T}b(\sigma(v)), $$ which contradicts to the fact that $\sigma$ is a permutation.

Therefore, there must be some $v$ with $\sigma(v)>v$, which means that $\sigma(v)$ is the best performer in $T$.

---

This idea can be realized simpler. I will not remove the induction solution though.

Take the pair $v$ with the maximum number of pairs directly beaten by it. Then it must be the best performer. This means that in vadim123's solution there is no need to consider the sets $V''$.

---

Another observation, which might be interesting. For an odd number $n$ of pairs, all pairs can be best performers: just let the pair number $k$ beat the pairs $k+1$, $k+2$, $\dots$, $k+(n-1)/2$ $(\operatorname{mod} n)$. For an even number $n$ of pairs, it is not possible that all pairs are best. However, all except one can be best (just take example for $n-1$ and let them all beat the remaining pair).