Grouping Problem

Question

Suppose there are 9 strangers. We will assign them into 3 groups and each group has exactly 3 people. For each grouping, the strangers who were assigned into the same group will get to know each other and they are not mutual stranger anymore. In the next grouping, the people that has known each other in the previous grouping, will not be assigned into the same group again.

How many times of grouping that we could possible make? (Which means at the end, it is not possible to form 3 groups that all of member in each group are mutual stranger)

Update: what if the number of stranger is m, and the number of group are n and m =3n

Answer 1

Four:

ABC DEF GHI ADG BEH CFI AEI BFG CDH AFH BDI CEG

We know this to be maximal: at the end, everyone is acquainted with everyone, so no improvement is possible.

---

For other $n$, I'm not exactly sure what we can do. It's clear that for $n=2$ we only get one matching, because any trio will now be guaranteed to have a pair from one or the other original matchings. Some thoughts:

• For $n\nmid 3$, we can't get "horizontal" as well as "vertical" matchings: if we imagine the people to be arranged in three rows of $n$ seats, we can certainly always match the people in the same column of seats, but the people in the same row will only match with each other if it's divisible by 3.
• For odd $n$, a staggered approach -- to perform the next matching, everyone in the front row moves right one seat and the guy kicked off the end loops around to the left end, and everyone in the back row moves left one seat, and then match by columns again -- works to match each person in each row with all the people in the other rows; this doesn't work for even $n$, where we'll only get half as many (try it with $n=4$, you'll see what I mean). This covers $n$ matchings for odd, or $n/2$ for even.
• For $n=3^q$, we do get complete coverage, and $\frac{3n-1}{2}$ matchings: the staggered approach covers relationships between rows, and then we can take each row and rearrange it into another set of three rows and apply the staggered approach again, until we've exhausted all of them.

---

That last one could use a little explaining, I guess. I'll do the case for $n=9$.

So first we arrange it in three rows:

ABCDEFGHI JKLMNOPQR STUVWXYZ@

And this gives groups like AJS BKT ... IR@ and AKU BLV ... IJT, and so forth, for nine total groupings.

Then we take each row and turn it into a group of three rows:

ABC JKL STU DEF MNO VWX GHI PQR YZ@

And go through each of these three groups the same way, then concatenating the results from each group. So from this we get ADG BEH CFI JMP KNQ LOR SVY TWZ UX@, AEI BFG CDH JNR KOP LMQ SW@ TXY UVZ, and AFH BDI CEG JOQ KMR LNP SXZ TV@ UWY.

Then finally we take each row in each of these groups and make that three rows:

A D G J M P S V Y B E H K N Q T W Z C F I L O R U X @

And then arranging those we only get one matching, which should be obvious.