The tournament involves $2k$ tennis players they play the tournament, each played with each exactly once. What is the minimum number of rounds you need to play to find 3 such that everyone plays with everyone?

In each round, $k$ games are played. I proved that if $k ^ 2 + 1$ edges will be drawn in a graph of $2k$ vertices, then a triangle is sure to exist, that is, if $k + 1$ round is held. And how to prove that $k$ rounds is not enough, I did not understand, I predict that this is proved by induction.

  • 1
    $\begingroup$ Please put $ signs around all math expressions, so that the formatting will take effect. I've done it for you here. You can edit the question to see what I've done, if the preceding sentence isn't clear. $\endgroup$ – saulspatz Feb 27 '19 at 16:32
  • $\begingroup$ Thanks a lot!!! $\endgroup$ – Yaroslav Feb 27 '19 at 16:35

Make a bipartite graph $K_{k,k}$, here we have $k^2$ edges and no triangles.

So you have two groups of size $k$ with no plays beteween players in the same group and each pair or players from different group played a game. So $k^2+1$ is a minimum.

One way to see that $k^2+1$ works is to use Turan theorem, which says that if graph on $n$ vertices doesn't have a triangle, then $\varepsilon \leq {n^2\over 4}$. But of course, this could be easly proved with induction with no use of Turan.


To prove that $k$ rounds does not force a triangle, consider the following set of matchesamong $2k$ players:

Divide the players $P_i: i = 1 \ldots 2k$ into equi-numerous groups $A = \{P_i : i \leq k\}$ and $B = \{P_i : i > k\}$. Then consider the following $k$ rounds of matches:

Every player in $A$ has played a match against each player in $B$ and no other match.

It is easy to show in that case that every player in $B$ has also played $k$ matches. So this is $k$ full rounds.

Yet this has no triangles.


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.