How to group people so everyone meets?

Solution 1:

Denote $M+1$ the max number of friends per group, $N+1$ the number of people, and $S_{k}$ the minimum number of meetings required for $k$ people. There are ${N+1\choose 2}$ pairs of people which need to meet. We eliminate at most $M+1 \choose 2$ of these pairs per meeting. Hence $S_{N+1} \geq \lceil {N+1\choose 2}{M+1 \choose 2}^{-1} \rceil$.

Applying the identity

\begin{equation} n = \lceil \frac{n}{m} \rceil + \cdots + \lceil \frac{n-m+1}{m} \rceil \end{equation}

for all integers $n$ and positive integers $m$, counting with induction gives

\begin{align} S_{N+1} &\leq S_{N} + \lceil \frac{N}{M}\rceil \\ &\leq \cdots \leq \lceil\frac{N}{M} \rceil + \lceil\frac{N-1}{M} \rceil + \cdots + \lceil \frac{M}{M} \rceil \\ &=\left(\lceil\frac{N}{M}\rceil + \cdots + \lceil \frac{N-M+1}{M} \rceil\right) +\left(\lceil\frac{N-M}{M}\rceil+\cdots+\lceil\frac{N-2M+1}{M}\rceil \right) + \cdots \\ &\leq N + (N-M) + (N-2M) + \cdots + (N-\left(\lfloor N/M \rfloor -1\right)M) \\ &=N\lfloor \frac{N}{M} \rfloor- M\lfloor \frac{N}{M} \rfloor \left(\lfloor \frac{N}{M} \rfloor - 1 \right)2^{-1} \\ &=\lfloor \frac{N}{M} \rfloor\left(N - \frac{M}{2} \left(\lfloor\frac{N}{M}\rfloor -1 \right) \right) \\ &\leq \frac{N}{M}\left(\frac{N}{2} + M\right) \\ &=\frac{N(N+2M)}{2M} \end{align}

where the first $\leq$ followed by induction, the second by appending the missing terms to the final grouped summation. Lastly \begin{equation} \lceil \frac{N(N+1)}{M(M+1)} \rceil \leq S_{N+1} \leq \lfloor \frac{N(N+2M)}{2M} \rfloor \end{equation}

The upper bound is rather large. It can be improved somewhat by assuming person $k+1$ has already met people from an earlier person's turn and doing the same computation.

$\textbf{Edit}$: A strategy like this is person $k+1$'s first meeting always includes $k$ and preferrably people $k$ has not met with numbers less than $k-1$. Then $k$ has always already met at least $M-1$ of the remaining people on their turn.

Similarly by induction

\begin{equation} S_{N+1} \leq \lceil \frac{N}{M} \rceil + \lceil \frac{N-M}{M} \rceil + \lceil \frac{N-M-1}{M} \rceil + \cdots + \lceil \frac{1}{M} \rceil \\ \end{equation}

which is the previous calculation with $N$ replaced by $N-M$ plus $\lceil \frac{N}{M} \rceil + M-1$. So

\begin{equation} S_{N+1} \leq \lfloor \frac{(N-M)(N+M)}{2M} + \frac{N}{M} + M \rfloor = \lfloor \frac{(N+1)^2+M^2-1}{2M} \rfloor \end{equation}

$N = 14, M = 5$ gives $7 \leq S_{15} \leq 24$.

Solution 2:

Hint: We can restate the problem as follows:

We consider a complete graph with $N$ vertices. The vertices of the graph represent the friends and since each two of them know each other we draw an edge between each two vertices, giving a complete graph.
A group of $6$ friends can be represented as complete subgraph of size $6$. Such a group is called clique and we are asking for the minimum number of $6$-size cliques which cover a complete graph of size $N$.

An answer to this question is given at math overflow. The paper Approximation algorithms for the k-clique covering problem might also be of interest.