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=\{a_1,a_2,\ldots ,a_k\}$ of positive integers such that every element in $A$ is divisible by $6$. 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 $A$ exists.
Problem
Source: Chinese Mathematical Olympiad 2000 Problem 3
Tags: combinatorics unsolved, combinatorics
randomusername
28.08.2015 23:52
$\frac12\max A+3$
Before doing anything useful, let's understand what is going on. We want to form pairs in pingpong, well then let there be a graph $\mathcal{G}$ whose vertices are the players and where two players are connected if they play as a pair. Because of condition (i), each node has degree at most $2$. It is then easy to prove that $\mathcal{G}$ can be partitioned into disjoint cycles, paths and isolated vertices. Anyway, in such a graph on $v$ vertices and $e$ edges, we have $2v\ge \sum[\text{degree}]=2e$, $v\ge e$ $(*)$. Equality holds only if each degree is $2$.
Now it is the pairs, the edges who play games, so write on each edge how many games the corresponding pair plays in the tournament. Then the number of games a player with a given vertex has played is the sum of the numbers on the edges incident to the vertex - write that number on this vertex.
Let $\max A=a$. Take a vertex $x$ whose number is $a$.
Clearly, $x$ has an edge incident to it. If there is only one edge, it has $a$ written on it, and if there are two edges, then one of them has $\ge \frac a2$ written on them. Let $xy$ be the edge with $\ge \frac a2$ written on it.
The vertices of $\mathcal{G}$ other than $x,y$ determine at least $\frac a2$ edges, because the pair $xy$ plays exactly once with every other pair (condition (ii)). This gives us $\ge \frac a2+2$ vertices by $(*)$. Equality holds only when each degree is $2$ in the remaining graph and there are two edges from $x$, both with number $\frac a2$ on them. But this is impossible, because if $xy$ and $xz$ are edges in $\mathcal{G}$, then $z$ will have degree $\le 1$ in the subgraph without $x,y$. So there are more than $\frac a2+2$ vertices, namely $\ge \frac a2+3$ vertices.
So we look at $\mathcal{G}$, and want it to have as many edges as possible. How about giving it a truckload of triangles? OK from now on, $\mathcal{G}$ means something completely different.
The divisibility by $6$, condition (i) and possibly the yearning for simplicity leads us to send our $\frac12\max A+3$ players into $b$ clusters of three people. The pairs playing will be the $3b$ pairs formed by two players in the same cluster. Now, suppose there exists a graph $\mathcal{G}$ with $b$ vertices whose vertex degrees form the set $\frac{A}6$. Assign each cluster a vertex, and for any clusters $X=(x_1,x_2,x_3)$ and $Y=(y_1,y_2,y_3)$, if corresponding vertices are connected, let all the pairs $\{x_i,x_j\}$ and $\{y_k,y_\ell\}$ play against each other (giving $9$ games). Now if we consider the resulting set of games, condition (i) is clear, (ii) is immediate and (iii) holds because the pairs are only formed within clusters. Moreover, any player in a cluster with degree $d$ in $\mathcal{G}$ gets a total of $6d$ games, $6$ for each edge. Hence the set of games will be precisely $A$, as required.
Let's proceed to prove that such a graph $\mathcal{G}$ exists. Since $b=\frac16\max A+1$, what we need is the following theorem:
For any set of positive integers $D=\{d_1<d_2<\dots<d_k\}$ with $k\ge 2$, there exists a graph $\mathcal{G}$ with $d_k+1$ vertices whose degrees form the set $D$.
We prove this by double induction, first on $k$, then on $\max D$. For $k=1$, we just take a complete graph on $d_1+1$ vertices.
Let's take a vertex with degree $d_k$ and look at the graph remaining. It has $d_k$ vertices and is supposed to have the degree set $\{d_1-1<d_2-1<\dots<d_k-1\}$ or $\{d_1-1<d_2-1<\dots<d_{k-1}-1\}$. If $d_1-1$ is a positive integer, apply the inductive hypothesis to the first set. Else, we may take $d_k-d_{k-1}$ isolated vertices in the graph until there are only $d_{k-1}$ vertices left, and then we apply the inductive hypothesis to $\{d_2-1<\dots<d_{k-1}-1\}$. This completes the induction.
Hence the construction is doable and we are done!