Efficient way to rotate through partitions with subsets of size three

Question

I'm looking to generalize the following problem and solution.

Problem 0: You have a group of $n$ people that need to all meet each other in pairs (e.g. maybe they have to all shake hands or something) through the course of $n-1$ time slots. Describe an effective way to organize doing this. (For simplicity, assume $n$ is even.)

Solution 0: Create a line of $n/2$ pairs of chairs facing each other. Have everyone take a seat and designate one person to be the anchor. For the first time period, each person pairs off with the person sitting in the chair opposite of them. Each time a time period is over, the group rotates in the following way: everyone except the anchor moves to the seat immediately to their right (or if in the farthest right seat, then around to the farthest left seat on the opposite side), skipping over the anchor if/when needed. The anchor remains in the same seat the whole time. In this way, after $n-1$ iterations, every person will have paired off with every other person exactly once. (Note: If $n$ is odd, consider the case of $n+1$ where the extra is a "dummy" person whose partner is then "on break".)

So, the actual question/problem I have is how to do this with triples instead of pairs.

Problem: You have a group of $n$ people that need to all meet each other in triples through the course of $(n-1)/2$ (??) time slots. Describe an effective way to organize doing this. (For simplicity, assume $n$ is odd and divisible by 3.)

Clarification: Each pair of people needs to meet once. So once two people have been in a triple together, ideally they are not in another triple together later. (And again it might not be possible to avoid this happening, in which case minimizing such instances is preferred.)

As indicated by the (??), I'm not sure it can be done in $(n-1)/2$ periods. If not, then the minimal number of time periods (whatever that may be) is preferred. In particular, I'm looking for a description of an efficient rotation process once the initial groups of 3 have been formed.

Answer 1

For simplicity, assume $n$ is odd and divisible by $3$.

While a necessary and sufficient condition as given in Mike's answer is good to have, simply saying "the construction is too complicated to reproduce in an answer" does not preclude showing the simpler parts of that construction.

Theorems 5 and 6 in Ray-Chaudhuri and Wilson give explicit constructions of Kirkman triple systems on $3q$ and $2q+1$ points where $q=6t+1$ is a prime power. For $3q$ points, label them as $(x,j)$ where $x\in\mathbb F_q$ and $j\in\{0,1,2\}$; furthermore let $g$ be a primitive element of $\mathbb F_q$. Define triples $$Z=\{(0,0),(0,1),(0,2)\}\\ B_{i,j}=\{(g^i,j),(g^{i+2t},j),(g^{i+4t},j)\},i\in[0,t),j\in\{0,1,2\}\\ A_i=\{(g^i,0),(g^{i+2t},1),(g^{i+4t},2)\},i\in[0,6t)$$ Then one of the parallel classes (time periods) is $Z\cup\{B_{i,j}\}\cup\{A_i:\lfloor i/t\rfloor\text{ odd}\}$ where indices have their full range as defined above unless stated otherwise. $q$ parallel classes are obtained from this class by shifting (adding the same element of $\mathbb F_q$ to the first part of every element in every block). The remaining classes are made of an $A_i$ where $\lfloor i/t\rfloor$ is even and all its shifts.

---

For $2q+1$ points label them similarly as above, except that $j\in\{0,1\}$ and the last point is called $\infty$; let $m$ solve $2g^m=g^t+1$. One parallel class consists of blocks $$\{(0,0),(0,1),\infty\}\\ \{(g^{i+2kt},0),(g^{i+2kt+t},0),(g^{i+2kt+m},1)\},i\in[0,t),k\in\{0,1,2\}\\ \{(g^{i+m+t},1),(g^{i+m+3t},1),(g^{i+m+5t},1)\},i\in[0,t)$$ and all the rest are obtained by shifting, except that $\infty$ does not change.

Here is an illustration of these blocks and classes when $t=2$, so $q=13$, $g=2$ and $m=8$:

---

A Kirkman triple system on $9$ points is given by the parallel lines of the Hesse configuration: $$(012,345,678)\\ (036,147,258)\\ (048,156,237)\\ (057,138,246)$$

Answer 2

Let us deal with the case where $n=6k+3$ first, for some $k\in \Bbb N$. In this case, it is possible to achieve to make all pairs meet in the minimal number of $(n-1)/2$ time slots. This is known as a Kirkman triple system, and the possibility of doing this for all $n\equiv 3\pmod 6$ was proved by Ray-Chaudhuri and Wilson.

Next, let's examine the case $n=6k+1$. In this case, a Steiner triple system exists, meaning we can make a list of $n(n-1)/6$ triples of people such that each pair of people appear together in exactly one triple. Each time slot can accommodate at most $(n-1)/3$ triples, so it takes at least $n/2$ time slots to have all of these triples meet. This is always possible, except for the small cases where $n\in \{7,13\}$, as proved by Vanstone et al.

For the other congruence classes $\pmod 6$, I do not know what the state of the art is. Given an $n$ not of the the previous forms, one thing you could to is to find the smallest $m$ such that $m\ge n$ and $m=6k+1$ or $6k+3$ for some $k$, and use the previous constructions, where you add in $m-n$ "dummy" people. Whenever a triple is scheduled that uses a dummy person, you either substitute some random other person, or just have the pair meet together.

Here are the sources where the constructions are described. They are too complicated for me to reproduce in this answer.

Ray-Chaudhuri, D. K. and Wilson, Richard M., "Solution of the Kirkman Schoolgirl Problem", Proceedings of Symposia in Pure Mathematics, 1971, Vol 19, https://doi.org/10.1090/pspum/019

Vanstone, Stinson, Schellenberg, Rosa, Rees, Colbourn, Carter, Carter. "Hanani triple systems." Israel Journal of Mathematics, 83(3), 305–319. https://doi.org/10.1007/BF02784058