Tricky (extremal?) combinatorics problem

Question

Apologies for being unsure the best way to express this problem.

I have 9 tables with 4 students at each table. I want to re-seat all students so no two students who have sat together ever sit together again. What's the maximum possible number of re-seatings?

Generally, given a set S of students partitioned into n disjoint subsets of k elements each, what's the maximum number of times I can permute the elements of S such that no two elements are members of the same subsets more than once. (I think that's what I want to be asking).

If anyone can point me in the right direction or provide illumination, it would be greatly appreciated!

Answer 1

The keyword here is block design (and resolvable block designs).

Update: The maximum number of rounds is between $9$ and $11$.

• Person 1 sits with $3$ distinct people in each round, so we can have at most $\lfloor (36-1)/3 \rfloor=11$ rounds. (We could similarly argue that there are $\binom{36}{2}$ pairs and pairs are used $9\binom{4}{2}$ at a time, giving $\leq 11$ possible rounds.)

• $9$ rounds is possible, and can be constructed as follows:

  • Step 1: Take three mutually orthogonal Latin squares of order $9$ (which exist; in fact, a finite field construction gives $8$-$\mathrm{MOLS}(9)$ (ref.)). Call these $L_1,L_2,L_3$ and assume $L_1$ uses the symbol $\{1,\ldots,9\}$, $L_2$ uses the symbol $\{10,\ldots,18\}$ and $L_3$ uses the symbol $\{19,\ldots,27\}$.

  • Step 2: Take the "union" of these matrices to form a $9 \times 9$ matrix in which each cell $(i,j)$ contains $\{L_1[i,j],L_2[i,j],L_3[i,j]\}$.

  • Step 3: Add symbol $28$ to the sets in the first column, $29$ to the sets in the second column, and so on, up to $36$ in the last column.

  We can check there are no pairs that occur twice case-by-case: if $x$ and $y$ (with $x \neq y$) occurs in two sets, then either (a) $(x,y)$ occurs in some $(L_i,L_j)$ twice, contradicting the orthogonal property, or (b) both $y$s occur in the same column, either contradicting that the $L_i$s are Latin squares, or contradicting $x \neq y$.

As a specific example:

[[28,1,10,19],[29,4,13,22],[30,7,16,25],[31,2,11,20],[32,5,14,23],[33,6,15,24],[34,3,12,21],[35,9,18,27],[36,8,17,26]]
[[28,4,16,23],[29,7,10,24],[30,1,13,20],[31,5,15,27],[32,6,11,26],[33,2,14,21],[34,9,17,22],[35,8,12,25],[36,3,18,19]]
[[28,7,13,26],[29,1,16,21],[30,4,10,27],[31,6,14,25],[32,2,15,19],[33,5,11,22],[34,8,18,24],[35,3,17,20],[36,9,12,23]]
[[28,2,12,22],[29,5,18,25],[30,6,17,19],[31,3,10,23],[32,9,13,24],[33,8,16,20],[34,1,11,27],[35,4,14,26],[36,7,15,21]]
[[28,5,17,24],[29,6,12,20],[30,2,18,23],[31,9,16,26],[32,8,10,21],[33,3,13,27],[34,4,15,25],[35,7,11,19],[36,1,14,22]]
[[28,6,18,21],[29,2,17,27],[30,5,12,26],[31,8,13,19],[32,3,16,22],[33,9,10,25],[34,7,14,20],[35,1,15,23],[36,4,11,24]]
[[28,3,11,25],[29,9,14,19],[30,8,15,22],[31,1,12,24],[32,4,18,20],[33,7,17,23],[34,2,10,26],[35,5,13,21],[36,6,16,27]]
[[28,9,15,20],[29,8,11,23],[30,3,14,24],[31,4,17,21],[32,7,12,27],[33,1,18,26],[34,5,16,19],[35,6,10,22],[36,2,13,25]]
[[28,8,14,27],[29,3,15,26],[30,9,11,21],[31,7,18,22],[32,1,17,25],[33,4,12,19],[34,6,13,23],[35,2,16,24],[36,5,10,20]]

It's not clear to me if more rounds than this would be possible.

---

I wrote some code that found a bajillion random $8$-round examples, e.g.:

[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16],[17,18,19,20],[21,22,23,24],[25,26,27,28],[29,30,31,32],[33,34,35,36]]
[[1,7,20,32],[2,5,17,29],[3,8,9,15],[4,18,26,34],[6,12,16,28],[10,22,30,35],[11,24,31,33],[13,19,21,27],[14,23,25,36]]
[[1,8,23,29],[2,10,14,33],[3,6,21,26],[4,12,13,22],[5,20,28,31],[7,11,27,35],[9,16,18,25],[15,19,32,34],[17,24,30,36]]
[[1,11,15,28],[2,7,18,30],[3,16,22,29],[4,9,27,33],[5,19,26,36],[6,10,20,25],[8,14,24,34],[12,17,21,31],[13,23,32,35]]
[[1,12,24,27],[2,8,19,31],[3,11,32,36],[4,16,20,35],[5,9,14,22],[6,15,30,33],[7,17,23,26],[10,13,18,28],[21,25,29,34]]
[[1,13,26,31],[2,16,23,34],[3,5,25,35],[4,10,15,36],[6,18,22,27],[7,12,19,33],[8,17,28,32],[9,20,24,29],[11,14,21,30]]
[[1,16,21,36],[2,11,22,26],[3,10,31,34],[4,19,23,28],[5,18,32,33],[6,9,13,17],[7,15,24,25],[8,20,27,30],[12,14,29,35]]
[[1,17,22,25],[2,15,21,35],[3,13,20,33],[4,7,14,31],[5,10,23,27],[6,11,19,29],[8,12,18,36],[9,28,30,34],[16,24,26,32]]

None of these $8$-round examples were extendable.

The random examples made it look like finding a $9$-round example this way would be difficult -- there were very few possible table combinations remaining, let alone finding $9$ simultaneous table combinations including every person. In the above example, for instance, no valid table can be formed with person $6$.

Answer 2

This is the social golfer problem. Here's the maximal solution for 9 groups of 4.

day 1:  BCNP    HRlm    Dkor    Fhnp    AJaj    KLEG    QIcd    Mbfi    Oqeg
day 2:  CDOQ    IAmn    Elpa    Gioq    BKbk    LMFH    RJde    Ncgj    Prfh
day 3:  DEPR    JBno    Fmqb    Hjpr    CLcl    MNGI    AKef    Odhk    Qagi
day 4:  EFQA    KCop    Gnrc    Ikqa    DMdm    NOHJ    BLfg    Peil    Rbhj
day 5:  FGRB    LDpq    Hoad    Jlrb    ENen    OPIK    CMgh    Qfjm    Acik
day 6:  GHAC    MEqr    Ipbe    Kmac    FOfo    PQJL    DNhi    Rgkn    Bdjl
day 7:  HIBD    NFra    Jqcf    Lnbd    GPgp    QRKM    EOij    Ahlo    Cekm
day 8:  IJCE    OGab    Krdg    Moce    HQhq    RALN    FPjk    Bimp    Dfln
day 9:  JKDF    PHbc    Laeh    Npdf    IRir    ABMO    GQkl    Cjnq    Egmo
day 10: BEch    DGej    FIgl    HKin    JMkp    LOmr    NQob    PAqd    RCaf
day 11: CFdi    EHfk    GJhm    ILjo    KNlq    MPna    ORpc    QBre    ADbg