Distributing 6 persons in their shifts evenly with rotating partner

Question

I thought this was easy but I was mistaken.

I need to make a schedule for 6 persons. They have to make shift by two (partner) but the partner should also rotate so that all person gets to be partnered with everyone else.

The first set was easy.

staff1 - staff2
staff3 - staff4
staff5 - staff6

Now when I reach the second set, it becomes problematic. Ideally, staff1 and staff2 should now start the shift on second set. But They should not be in the same partnership this time.

Any idea how to fairly distribute it? Is there a formula that can be use in this case?

Thanks

Answer 1

There are ${6\choose2}=15$ different pairs $jk$, and each day consumes three of them. Consider these pairs as sides and diagonals of a regular hexagon $H$ with vertices $\{1, \ldots,6\}$. You have produced the first day list $d_1=(12,34,56)$. Rotate $d_1$ by $60^\circ$, meaning: add $1$ to each entry, and obtain $d_2=(23,45,61)$. Now take the pattern $d_3=(14,26,35)$, and rotate it $2$ times by $1$. In this way you obtain $d_4=(25,31,46)$ and $d_5=(36,42,51)$. Now each side or diagonal of $H$ appears exactly once in a $d_i$ $(1\leq i\leq 5)$.

Answer 2

(this is a footnote rather than an answer)

a choice of shift partners for a single day can be represented as an element of the symmetric group $S_6$. for example $\tau = (1 2) (3 4) (5 6) = t_{12}t_{34}t_{56} $.

the conjugacy class of $\tau$ has fifteen elements, and the centralizer of $\tau$ in $S_6$ is a group of order 48 isomorphic to $C_2^3 \times S_3$.

this links the problem to one of the most arcane topics in elementary group theory - the exceptional (because outer) automorphism of $S_6$. in this paper about the automorphism the author gives a sequence which bears on OP's question:

$$ 12 \quad 35 \quad 46 \\ 23 \quad 14 \quad 56 \\ 34 \quad 25 \quad 16 \\ 45 \quad 13 \quad 26 \\ 15 \quad 24 \quad 36 \\ $$