How many combinations of groups are there where no member of a group has been with another member before?

Question

I found this hard to word in the title, so let me give an example.

I have 16 students, and I want to split them up into 4 groups of 4. However, I want to make sure that every time I have a new combination of groups, that a student has never been with any of their new groupmates before.

I found info on how to separate objects into groups, but not in only unique ways as I've described above.

I think I figured this out the rote way, by assigning each student a number and then finding the unique combinations, and got 3. But I'd like to know the math behind it, and how it could be applied to other configurations (20 students w/ 4 groups of 5?).

Thanks for any help you can give!

Answer 1

I think there are $5$ ways to do it, not $3$.

Identify each student with one of the $16$ points of the affine plane over the field with $4$ elements. To divide the students into $4$ groups, we can group them according to a pencil of $4$ parallel lines. Then the question becomes, "How many parallel directions are there in the plane?"

Of course, this is just the number of lines through the origin. We can join the origin to any of the other $15$ points, but each line is counted $3$ times, once for every point on it other than the origin, so there are $5$ lines.

In general, this is a problem in combinatorial designs, and there are a lot of open questions, I believe.

EDIT

Here is a python script that computes the answer. I don't know how to draw a comprehensible picture of the plane over $\mathbb{F}_4$. I think of a $4\times4$ array of dots for the points. The problem is that there are $20$ lines, and I don't see how to draw them without making a mess.

Here is my script:

plus = { }

for x in range(4):
    plus[x,0] = plus[0,x] = x
for x in range(4):
    plus[x,x] = 0
plus[1,2]=plus[2,1] =3
plus[1,3]=plus[3,1] = 2
plus[2,3]=plus[3,2] = 1

times = { }
for x in range(4):
    times[x,0]=times[0,x] = 0
    times[x,1]=times[1,x] = x
    times[2,2] = 3
    times[3,3] = 2
    times[2,3]=times[3,2] = 1
    
points = set(range(1,16))  # points that have to be with 0

def add(x,y):
    x0, x1 = divmod(x,4)
    y0, y1 = divmod(y,4)
    a = plus[x0, y0]
    b = plus[x1,y1]
    return 4*a+b
    
def mult(k, x):
    x0, x1 = divmod(x,4)
    a = times[k, x0]
    b = times[k, x1]
    return 4*a+b

def plane(pt):
    answer = 4*[None ]
    answer[0] = sorted([0, pt, mult(2,pt), mult(3,pt)])
    used = set(answer[0])
    for n in range(1,4):
        for x in range(16):
            if x not in used: break
        answer[n] = sorted([add(x, y) for y in answer[0]])
        used |= set(answer[n])
    return answer
    
planes = []    
while points:
    x = points.pop()
    p = plane(x)
    planes.append(p)
    for pt in p[0]:
        points.discard(pt)
        
for plane in planes:
    for line in plane:
        print(line)
    print()
    
for x in range(16):
    for y in range(16):
        if x==y: continue
        found = False
        for plane in planes:
            if found:
                break
            for line in plane:
                if x in line and y in line:
                    found = True
                    break
else: # not found
    print(f'Did not find {x}, {y}')
      

This produced the output

[0, 1, 2, 3]
[4, 5, 6, 7]
[8, 9, 10, 11]
[12, 13, 14, 15]

[0, 4, 8, 12]
[1, 5, 9, 13]
[2, 6, 10, 14]
[3, 7, 11, 15]

[0, 5, 10, 15]
[1, 4, 11, 14]
[2, 7, 8, 13]
[3, 6, 9, 12]

[0, 6, 11, 13]
[1, 7, 10, 12]
[2, 4, 9, 15]
[3, 5, 8, 14]

[0, 7, 9, 14]
[1, 6, 8, 15]
[2, 5, 11, 12]
[3, 4, 10, 13]  

Did not find 15, 15

Where the last line is a spurious error message due to sloppy programming.

EDIT

In response to user's comments.

I thought of a way to present this that might make it a little clearer. In each group, the $16$ numbers represent the points of the plane, and points of the same color lie on the same line. In the first two groupings, this looks pretty dull; the lines are rows or columns. In the last three groupings, the lines don't look like what we normally think of as lines, but they satisfy the same kind of linear equations as the lines you're used to.

This isn't the place to try to explain that. You can search the Web for "finite geometries", but you'll have to learn a little bit about finite fields before it makes sense.

Answer 2

There are at least 4 ways to do it for 4 groups of 4. I'm not sure if it's possible to do more, or about how to extend to larger groups.

Answer 3

If you have $n^2$ students being divided into $n$ groups of size $n$, then a solution which works for $d$ ways is equivalent to a set of $d+2$ mutually orthogonal $n\times n$ Latin squares (MOLS). Some partial results:

• For any $n$, you can succeed for at most $n+1$ days.

• When $n$ is a prime power, it is possible to achieve the limit of $n+1$ days.

• For $n=6$, three days is the max, as there are no two orthogonal $6\times 6$ Latin squares.

• For $n=10$, four days is possible, but it is an open problem to determine if five days is possible (see Find three $10\times10$ orthogonal Latin squares.).

• There is more data on the maximum known number of MOLS here: http://www.math.stonybrook.edu/~tony/whatsnew/column/latin-squaresII-0901/latinII3.html

In general, if you have $nm$ students to be divided into $n$ groups of size $m$, this is known as the Social Golfer problem. Again, this is a hard open problem in most cases. See

http://www.mathpuzzle.com/MAA/54-Golf%20Tournaments/mathgames_08_14_07.html

for some partial results, and you can find more by searching "Social Golfer problem."