$n$ Tennis players took part in the one-round table tennis tournament $(n \geq 3)$. We say that player $A$ is better than player $B$, if ...

166 Views Asked by At

$n$ Tennis players took part in the one-round table tennis tournament $(n \geq 3)$. We say that player $A$ is better than player $B$, if $A$ won $B$ or there is such a player $C$, that $A$ won $C$, and $C$ won $B$. For what $n$ in the tournament could it be that each player is better than everyone else? There are no draws in tennis.

I proved that $n = 3k$ is suitable, I also learned how to make an example for $n = 5$, I assume that $n = 3k + 2$ is suitable, but I cannot prove it, it is also not clear what to do if $n = 3k + 1$.

1

There are 1 best solutions below

0
On BEST ANSWER

Partial solution... specifically:

Claim A: Any odd $n$ is feasible.

Claim B: $n = 4$ is infeasible.

Proof of A: Arrange the players in a circle and number them $0, ..., n-1$, and let $i$ beat $i+1, i+3, ..., i+n-2$. All arithmetic is modulo $n$.

First of all, this assignment is consistent: For any $i \neq j$, if $j = i + odd$ (i.e. $i$ beats $j$) then $i = j + even$ (i.e. $j$ does not beat $i$).

Next, clearly $i$ beats all the $i+odd$ directly, but since each $j$ beats $j+1$, $i$ also indirectly beats all the $i+odd+1$, i.e. all the $i+even$.

Proof of B: Among the $n=4$ players, clearly nobody can beat everyone or be beaten by everyone. Since each plays $3$ games, that means each must win only $1$ or $2$ games. Since there are $6$ games total, the only way to do this is if two players $W,X$ win twice each and two other players $Y,Z$ win once each. But consider the match between $Y,Z$ and without loss assume $Y$ beats $Z$. This is $Y$'s only win, and $Z$ beats only $1$ person (e.g. $W$), so $Y$ does not directly nor indirectly beat the other person (e.g. $X$).