Maths Olympiad Prep

Library / /89 of 144

Combinatorics Difficulty 8.4 Shortlist Find the answer

An (n,k)\minus (n, k) \minus{} tournament is a contest with n n players held in k k rounds such that:

(i) (i) Each player plays in each round, and every two players meet at most once.
(ii) (ii) If player A A meets player B B in round i i, player C C meets player D D in round i i, and player A A meets player C C in round j j, then player B B meets player D D in round j j.

Determine all pairs (n,k) (n, k) for which there exists an (n,k)\minus (n, k) \minus{} tournament.

[i]

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve the problem of determining all pairs (n,k)(n, k) for which there exists an (n,k)(n, k)-tournament satisfying the given conditions, we need to consider each part of the problem systematically.

### Conditions to Satisfy:

1. Each player participates in every round, and any two players meet at most once throughout the tournament.
2. The tournament respects an additional condition:
- If player A A meets player B B in round i i , player C C meets player D D in round i i , and player A A meets player C C in round j j , then player B B must meet player D D in round j j .

### Analysis:

- Condition (i) suggests that an (n,k)(n, k)-tournament should be such that any pair of players meets exactly once per round and never more than once in the entire tournament.

- Condition (ii) imposes a structural constraint often associated with matrices having the property that the arrangement of meetings of some players determines the meetings of other players.

### Insight and Solution:

A classical construction that satisfies such properties corresponds to using finite fields and projective geometries, particularly focusing on powers of 2. This relationship is due to the symmetric properties and existence of designs that fit these constraints when n n is a power of 2.

1. **Finding n n :**
- The constraint that each pair of players meets at most once can be interpreted using a combinatorial design, specifically a projective plane structure or its variants.
- If n n is power of 2, say n=2t n = 2^t , this structure is readily available within the framework of binary finite fields.

2. **Finding k k :**
- A maximal construction occurs when k2t1 k \le 2^t - 1 . This stems from the number of distinct elements required to ensure unique pairings and the symmetric nature of such tournaments, which dictates a similar maximum number of rounds due to the pairing conditions and transitive triangle implications outlined in condition (ii).

Therefore, the solution is that there indeed exist (n,k)(n, k)-tournaments:
n=2tandk2t1. n = 2^t \quad \text{and} \quad k \le 2^t - 1.

### Conclusion:
The solution for the existence of an (n,k)(n, k)-tournament, based on efficient pairing and meeting conditions, yields:
n=2t and k2t1. \boxed{n = 2^t \text{ and } k \le 2^t - 1.}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.