14
$\begingroup$

In a tournament without draws, every two of the nine teams play against each other exactly once. Must there always be two teams such that every other team has lost to either or both of them?

From the Kindle sample of the book "Grade five competition from the Leningrad Mathematical Olympiad".

$\endgroup$
2
  • $\begingroup$ I only have the Kindle sample of the book. The sample has some very interesting problems..Do consider downloading the Kindle sample. $\endgroup$ Aug 14, 2023 at 20:57
  • $\begingroup$ Does this relate in any way to non-transitive dice? $\endgroup$
    – Jiminion
    Aug 17, 2023 at 19:54

5 Answers 5

27
$\begingroup$

Answer:

No, there is a counterexample.

Explanation:

Consider a "rock-paper-scissors squared" setup where each team plans two throws of rock, paper, or scissors, with the 9 teams corresponding to the $3^2$ pairs of throws. The winner of each match is the rock-paper-scissors winner of the first throws, or if those are the same, tiebroken by their respective second throws. No ties are possible, and each team beats 4 of the other teams, and loses to 4 of the other teams.
Let's see why, for any two teams, there's another team that beat both. If the two teams have the same first throw, say paper, then a team throwing scissors beat both. Otherwise, they have different initial throws, say, paper and scissors. Find the winner of those two throws, here scissors, and take the team whose first throw is scissors and whose second throw beats the scissors' team's second throw. That team beat both of them.


A natural follow-up question is whether there's any

smaller counterexample tournament using fewer than 9 teams

To this the answer is

Yes

Explanation:

Here's a construction with 7 teams. Have them stand in a circle, and each team beats the teams 1, 2, and 4 spaces to its left, and loses to the teams 1, 2, and 4 spaces to its right.
Now let's check that for any pair of teams, there's another team that beats them both. Call one of them Team 0, and label the team to its right as Team 1, and so on, and let Team N be the other chosen team. We limit N to 1, 2, or 3, by otherwise switching which of the teams is labelled Team 0. Then:
- Teams 0 and 1 both lose to Team 2
- Teams 0 and 2 both lose to Team 4
- Teams 0 and 3 both lose to Team 4

Seven teams is the minimum, as BlueHairedMeerkat shows.

$\endgroup$
7
  • 1
    $\begingroup$ I am unable to understand your solution . What is a rock paper scissors squared setup? What do you mean by, "So, the 9 teams correspond to the $3^2$ pairs of throws" . Please explain in simpler language. $\endgroup$ Aug 14, 2023 at 20:45
  • 10
    $\begingroup$ What a lovely example! @HemantAgarwal What is meant is that the 9 teams are RR, RP, RS, PR, PP, PS, SR, SP, and SS. Then, for example, RR will beat RS, SR, SP, and SS. Each team wins exactly half of their games, and there are no ties. $\endgroup$
    – DanDan0101
    Aug 14, 2023 at 22:19
  • 1
    $\begingroup$ @HemantAgarwal Albert Einstein: "Make everything as simple as possible, but not simpler." $\endgroup$ Aug 14, 2023 at 23:46
  • 5
    $\begingroup$ We can prove 7 to be optimal: in the case with 6 teams, take a team that has won at least three of its matches. It lost to at most two teams. If it lost to fewer than two, pick either the single team it lost to, or any team if it never lost. If it lost to two teams, choose the one of them that beat the other. $\endgroup$ Aug 15, 2023 at 9:29
  • 2
    $\begingroup$ @HemantAgarwal xnor constructed a case for 7, so we know that works. I showed 6 does not work; the key point of my argument is that there exists a team that lost to at most two other teams, which is true for any <=6. Hence 7 is the lowest value for which this can be done. $\endgroup$ Aug 16, 2023 at 9:13
22
$\begingroup$

Proof without words (inspired by xnor’s answer)

enter image description here

$\endgroup$
1
  • 2
    $\begingroup$ Simple, concise, and intuitive. This is the kind of answer that readers grasp most easily. $\endgroup$
    – iBug
    Aug 17, 2023 at 15:19
4
$\begingroup$

Mathematically, if we think of the outcome of the games as a directed graph (one node per team, edges representing who won each game), we get a type of graph called a tournament. A set S of nodes in a directed graph where each node is either in S or is at the end of an edge leaving S is called a dominating set, so this question is equivalent to the following:

Does every tournament have a dominating set of cardinality 2?

The other answers here have shown that the answer is

“no.”

More generally,

most tournaments don’t have dominating sets of size 2. This MathOverflow post summarizes some broader results about dominating sets in tournaments, including the fact that a random tournament with n players is very unlikely to have a dominating set of size less than lg n - 2 lg lg n.

$\endgroup$
4
$\begingroup$

The OP requested in a comment a proof for greater values., so here is a simple one.

@xnor and @BlueHairedMeerkat have shown that the minimal counter example is for 7 participants. I will show that for all n >= 7, there exists a counter example.

Start with the minimal counter example of 7 people.
Now to obtain counter example for n people, we can simply add n-7 participants and ensure that that they lose to each of the original 7 participants.
Now any pair from the original 7 still lose to one member of the original 7.
And swapping one of the pair for a newly added member doesn't help, since the newly added member loses to all of the original 7.

$\endgroup$
1
$\begingroup$

Is it necessarily the case?

No.

Why?

First of all, no one can beat more than $n-4$ teams in a tournament between $n$ participants for the conditions to remain unsatisfied, because if participant $t_1$ loses to two participants, the other participant $t_2$ can be picked as the one who has defeated the other, allowing $t_1$ and $t_2$ to collectively defeat everyone else. As such, if $n-3 <= ceiling[(n-1)/2]$, therefore $n<7$, the conditions are always satisfied.

For $n=7$, there are $21$ pairs of teams and no participant can win more than thrice, so every team must have won three times. If $t_1$ beats $t_2,t_3,t_4$ and loses to $t_5,t_6$ and $t_7$, and $t_5$ beats $t_6$, then $t_7$ beats $t_5$, and $t_6$ beats $t_7$. Because of the symmetry, we can assume that $t_5$ beats $t_2$ as well as $t_1$ and $t_6$, losing to $t_3,t_4$ and $t_7$. $t_6$ is bound to lose to at least one of $t_3$ and $t_4$, so let it be $t_3$. If we want the rule to be contradicted, $t_3$ must lose to $t_7$. For $t_2$ and $t_5$ to not cover everyone else, the former must beat $t_6$, meaning $t_6$ beats $t_4$. Then, for $t_3$ and $t_6$ to not cover everyone else, $t_3$ must beat $t_4$.

The list for wins will be this:

$t_1:t_2,t_3,t_4$
$t_2:t_3,t_6,t_7$
$t_3:t_4,t_5,t_6$
$t_4:t_2,t_5,t_7$
$t_5:t_1,t_2,t_6$
$t_6:t_1,t_4,t_7$
$t_7:t_1,t_3,t_5$

For larger $n$, just take this "core" of seven teams, add the new team to their wins and have it lose to everyone else. Rinse and repeat.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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