Maths Olympiad Prep

Library / /36 of 37

Combinatorics Difficulty 7.4 National olympiad, round 2 Find the answer

A table tennis club hosts a series of doubles matches following several rules:
(i) each player belongs to two pairs at most;
(ii) every two distinct pairs play one game against each other at most;
(iii) players in the same pair do not play against each other when they pair with others respectively.
Every player plays a certain number of games in this series. All these distinct numbers make up a set called the “*set of games*”. Consider a set A={a1,a2,,ak}A=\{a_1,a_2,\ldots ,a_k\} of positive integers such that every element in AA is divisible by 66. Determine the minimum number of players needed to participate in this series so that a schedule for which the corresponding set of games is equal to set AA exists.

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

Solution

To determine the minimum number of players needed to participate in the series such that the set of games is equal to the set A A , we start by analyzing the problem through graph theory.

Consider a graph G \mathcal{G} where each vertex represents a player and an edge between two vertices represents a pair of players. According to the problem's conditions:
1. Each player belongs to at most two pairs.
2. Every two distinct pairs play one game against each other at most.
3. Players in the same pair do not play against each other when they pair with others respectively.

Given these conditions, each vertex in G \mathcal{G} can have a degree of at most 2. This implies that G \mathcal{G} can be decomposed into disjoint cycles, paths, and isolated vertices.

Let maxA=a \max A = a . We need to ensure that there is a player who plays a a games, and each element in A A is divisible by 6. To achieve this, we need to construct a graph where the number of games each player plays corresponds to the elements in A A .

### Proof of Optimality
Let x x be a vertex with the maximum number of games a a . This vertex x x must be connected to at least one other vertex. If x x has only one edge, it must have a a games on it. If x x has two edges, each edge must have at least a2 \frac{a}{2} games.

Let xy xy be an edge with a2 \geq \frac{a}{2} games. The remaining vertices must account for at least a2 \frac{a}{2} edges, ensuring that there are at least a2+2 \frac{a}{2} + 2 vertices. However, due to the constraints, there must be at least a2+3 \frac{a}{2} + 3 vertices to satisfy all conditions.

### Construction
To construct such a graph, we can use clusters of three players, each forming pairs within the cluster. This ensures that each player in a cluster plays 6 games per edge. By assigning each cluster to a vertex in a graph G \mathcal{G} with b b vertices, where b=16maxA+1 b = \frac{1}{6} \max A + 1 , we can ensure that the set of games corresponds to A A .

Thus, the minimum number of players needed is:
12maxA+3. \frac{1}{2} \max A + 3.

The answer is: \boxed{\frac{1}{2} \max A + 3}.

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.