Maths Olympiad Prep

Library / /17 of 19

Combinatorics Difficulty 6.9 National olympiad Find the answer

In a tennis club, each member has exactly k>0k > 0 friends, and a tournament is organized in rounds such that each pair of friends faces each other in matches exactly once. Rounds are played in simultaneous matches, choosing pairs until they cannot choose any more (that is, among the unchosen people, there is not a pair of friends which has its match pending). Determine the maximum number of rounds the tournament can have, depending on kk.

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

Solution

Consider a tennis club where each member has exactly k>0 k > 0 friends. The task is to determine the maximum number of rounds in a tournament where each pair of friends plays exactly once. Matches in each round are simultaneous, meaning no participant can play more than one match per round. We need to find the maximum number of such rounds.

This problem is equivalent to finding a way to cover all edges of a k k -regular graph with the minimum number of matchings.

### Steps to Solve the Problem:

1. Graph Representation:
- Represent the club members as vertices in a graph.
- Each pair of friends is an edge, forming a k k -regular graph, meaning each vertex has degree k k .

2. Edge Matchings:
- We need to cover all edges of this k k -regular graph with matchings such that each round corresponds to a matching.
- A matching is a set of edges without common vertices, representing possible simultaneous matches in a single round.

3. Decomposition of the Graph:
- A k k -regular graph can be decomposed into k k edge-disjoint 1-factors, or matchings, if the number of vertices is even (by a theorem related to edge colorings or 1-factorization).
- For an odd number of vertices, the graph can't be perfectly decomposed into k k matchings due to the k k -regularity condition, necessitating additional matchings to cover all edges.

4. Maximizing Rounds:
- By Vizing's theorem, a simple k k -regular graph's edges can be colored using at most k+1 k+1 colors if k k is odd, which implies that at most 2k1 2k-1 rounds are needed in the worst case.
- The minimum rounds necessary is derived by assuming each match can involve a new combination of available matchings. Hence, factoring in overlaps or incomplete matchings in less than optimal conditions, a maximum of 2k1 2k-1 rounds could be required.

Thus, the maximum number of rounds the tournament can have, depending on k k , is:
2k1 \boxed{2k - 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.