How to group people so everyone meets? I have sort of a stupid maths problem which I was thinking about recently, given the UK's covid rules about only being able to meet with 6 people max.
If I have a group of $N$ friends (e.g. 15) and everyone wants to hang out with everyone else, what's the fewest number of meet-ups we would need to accomplish this (with max 6 people in each)?
This seems similar to the social golfer problem. Is it possible to come up with a general solution?
(obviously not planning to go and do this in person, but I was thinking about this and couldn't come up with a solution)
 A: 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$.
A: 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.
A: All members of a group are considered to have met each other.
In general, if we have $N$ people and the maximum group size is $k$, we can represent $N$ as
$N = \left\lfloor {k \over 2} \right\rfloor n + c$, where
$$c = N \mod \left\lfloor {k \over 2} \right\rfloor$$
This splits the $N$ people into $n+ (k \mod 2)$ subgroups of maximum size size $\left\lfloor {k \over 2} \right\rfloor$ each.
We can choose two subgroups and group them together into a group of size $2\left\lfloor {k \over 2} \right\rfloor \le k$.
The number of such combinations of subgroups is
$$C(n, 2)$$
For the case of $N = 15, k = 6$, we have
$$N = 15 = \left\lfloor 6 \over 2 \right\rfloor \times 5 = 3 \times 5 + 0$$
So, we have $n = 5, c = 0$ and the number of minimum meetups = $C(5, 2)$
