The school owner, Ken Green, could afford the best education for his kids in the original Green Private School, so he decided to have very small classes — eight students per teacher. To allow for a richer experience at each grade level he had 64 students, which were therefore divided into eight classes. This post discusses some further details of how students in a grade were divided into classes, focusing on a single class, created to satisfy Miri Green’s desire for a best friend.

*The version from before Recursive Exhaustion starts with a difficult attempt to gather the data:*

The children were given questionnaires and personal interviews, after which their interpersonal compatibility was estimated.

*The version from after Recursive Exhaustion. Without their parent’s permission, a vast amount of information about the children. There was no point in collecting less reliable information on their own, so they just use the results of this Very Large Scale Collection of Social Data.*

* That data will change with time, so there is no need to update it, though there might be some point in contributing to it. That couldn’t make the problem worse and might help make it better.*

Using either the original handcrafted technique or the much more reliable data which will be readily available, the first thing to do was create an interpersonal compatibility matrix.

This 64 by 64 weight matrix was used for weighted bipartite matching. The most compatible person for her in Miri’s grade turned out to be a girl named Celesta. The result of the bipartite matching was 32 pairs of students.

The next step was to produce a 32 by 32 matrix giving the compatibility between these pairs. The compatibility between one pair and another was taken as the *minimum* of the individuals. If one pair was Ann and Barbara, while the other pair was Cathy and Diane, then four comparisons would be made: Ann with Cathy, Ann with Diane, Barbara with Cathy, Barbara with Diane. The minimum of these was taken as the compatibility between those two pairs.

Given the 32 by 32 matrix of compatibility between pairs, weighted bipartite matching was used again. The result was the best set of pair-to-pair matches, which generated 16 sets of four students apiece. The same process was repeated one more time, generating eight sets of eight students. That is the desired division of the entire grade of 64 students into the desired eight small classes.

The result was a compromise between the teacher’s desire for a class of compatible students who would get along together in class, with little conflict, and the desire of students to have the best possible friends.

Of the 64 students in her grade, the most compatible was a girl her own age named Celesta. It did not take long for them discover how much they had in common, with just enough differences to make their relationship iuteresting.

As it happened, the class containing Miri and Celesta included another pair of best friends, Sonya and Althea. Taken as a pair, Miri and Celesta had Sonya and Althea as the best possible matching pair. Of the four estimated compatibilities, that of Sonya and Celesta was the least, so that was taken as the interpair estimate. Of all possible pair-to-pair matchings however, that of Miri and Celesta with Sonya and Althea was the best. At lunch time the four usually sat together around a table for four.

At this age, boys and girls did not get along well together, so this turned out to be a class of girls. The foursome containing Miri, Celesta, Sonya and Althea ended up being matched with a foursome containing Josephina, Latonya, Benita and Neva. Of all foursome-to-foursome matchings in the grade, this was the best of those which might contain Miri.

So, of the 4,426,165,368 ways of dividing 64 students into classes of eight, this was a plausible result of a well designed algorithm. Was it the best overall? Probably not, but it was a good try.

An alternative approach would be if the pair-to-pair compatibility was taken as the *maximum* of the four interpersonal comparisons. In that case the internal compatibility within a set of four might be quite low. We might find A <->B<->C<->D, where A and B are a pair, as are C and D, then the foursome was assembled by noting that B and C were highly compatible. In that case, however, there is no reason for assuming A and C, B and D, or A and D are at all compatible. Every person in the foursome has a least one good friend, and both B and C are lucky enough to have another, but there could be as many as three serious conflicts within the group.

It could be argued that conflict has a role, provoking discussion, and that as long as each person in the class has at least one close friend, it would be a good educational environment. That is a difficult matter to resolve, and proves that the class division problem is still an open problem.