2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What is a "one-round tournament"? Perhaps if you show the $n=5$ example I can better understand the tournament format? $\endgroup$ – antkam Mar 12 '19 at 13:20
  • $\begingroup$ one-round tournament is when everyone has played exactly one time with each $\endgroup$ – Yaroslav Mar 12 '19 at 13:26
  • 1
    $\begingroup$ Ah, thanks, what I usually call a "round-robin" tournament then. :) $\endgroup$ – antkam Mar 12 '19 at 13:28
  • 1
    $\begingroup$ @MikeEarnest maybe I'm missing something obvious, but how does a Rock beat (directly or indirectly) another Rock? I can see this happening if, among the Rocks, you use something like my $n=odd$ solution, but then if each of the 3 groups (no need for equal size) are odd numbered, then the total number is odd and you could have just used my solution to begin with. $\endgroup$ – antkam Mar 12 '19 at 18:00
  • 1
    $\begingroup$ @MikeEarnest - Your RPS idea does imply this: If some even $n$ is feasible, then any larger even $N > n$ is also feasible, because you can always divide $N-n$ into two odd groups and use my solution for each. $\endgroup$ – antkam Mar 12 '19 at 20:01
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.