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!
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