Tricky (extremal?) combinatorics problem

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!

Solutions Collecting From Web of "Tricky (extremal?) combinatorics problem"

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$.

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