The Breakout Room Puzzle

This challenge was given to me by my future daughter-in-law, Audrey, as a genuine need.  She had a large meeting of people (16) during which she wanted to break them into smaller groups (e.g. of 4 each) so that they could get to know each other more personally.  After each small meeting, they would mix it up and do it again. The question was, how to do this with the minimum number of (parallel) break-out sessions?

From an individual’s perspective, they have 15 people to meet, and would be meeting 3 in each breakout session so 5 sessions should suffice.  It is easy to arrange a schedule of six meetings to accomplish this, but finding a schedule of only 5 sessions proves more challenging.  Is there an elegant solution?

Firstly, how many pairings do we need to make?  N people must each meet N-1 others, so we have N(N-1)/2 pairs to create.  For 16 that means 120 total introductions to be made.  In each x-person breakout there are (x-1) factorial pairs matched up so 3x2x1 = 6 introductions in the 4-person breakout example given.  120/6, then divided by 4 simultaneous breakouts gives a theoretical minimum of the same 5 sessions we arrived at earlier.

To find such a schedule, I had to put on my Sudoku hat and work out an example solution by trial and error, given below.  However, the challenge is, for arbitrary numbers of total participants and number of smaller breakout rooms, is there an elegant solution?  This is the mathematical puzzle left for the reader to solve.

~~~~~~~~~~~~~~~~~~~

Solution for 16 participants, 4 breakout rooms (north, south, east, and west):