In the novel Society Changed and its predecessor, The Green Family Chronicles, the family starts a school for its many children. One of the serious questions is how the children will be divided into classes. It is specified that each grade will have 64 students. There will never be enough Green Family members to fill a grade, but the addition of outside students is considered a good idea. Since Ken Green is a rich man and can afford to staff a school luxuriously with many teachers, the kids are to be taught in very small classes, just eight students per class. The question then is how to divide the 64 children in each grade into eight classes of eight. There are in fact 4,426,165,368 different ways to do this. One way is discussed in this excerpt from the book:
The Green Private School due to open in September would have one special person it. A member of the Green family, she was not Ken’s daughter but his niece.
Ken planned to make sure Miri was admitted to the school whether or not she passed the entrance exams, but he was sure she’d do well on them. A bright girl, well educated by private tutors, Ken thought she would be above even talented kids of her own ages. He believed she could skip a grade, perhaps two.
Miri Green was now 11, in the midst of puberty, and experiencing new feelings, but she had not been exposed to any children near her age, and indeed, no male person except her uncle or his sons, the oldest being five. In this vacuum, Miri had seemed capable of ignoring all her urges and acting, maybe even feeling as if puberty had not begun. She was quiet and sweet, not as playful as she had once been, but adorable. Ken felt her the nicest girl of her age he had ever met.
Before school started, Ken had approached Miri to speak with her about the school. “You are young, Miri, but you are bright and we’ve had fine tutors for you. A girl your age should be going into grade 6, but you know so much, that seems a waste. We should put you in grade 8, or at least grade 7.”
For once in her life, Miri dared to contradict him. “No, Uncle Ken, please, not that. All I want is to be with those my own age. It is what I dream about.”
“Oh, Miri, Miri, what have I done? How stupid I’ve been. Of course you need the company of people your own age. Forgive me for being so blind. We’ll put you in grade 6, with other 11 year olds. They won’t know as much as you do, but I’m sure they’ll welcome you as their friend.”
“Thank you, Uncle Ken”, said Miri, tears forming in her eyes. “All I’ve ever wanted is friends.”
Ken put his arms around Miri and cried, ashamed of himself for treating her so badly.
Later, Ken talked to his best friend, who would turn five about a month after school opened.
“Beth, I feel so ashamed of myself. I was going to put Miri in a grade a year or two ahead of her age level, and she begged me not to. She said she’d dreamed about being with people her own age, and that all she had ever wanted was friends. I deprived her of that. I should have known how she would feel. How could I be so insensitive?”
“Did you have friends at her age?”
“Oh, yes, I had two friends, wonderful friends. Gwen and Gayle.”
“That’s funny, those sound like girl’s names. Your two friends weren’t both girls were they, Daddy?”
“I see. Well, Daddy, about Miri. I’m not sure what you could have done differently, but the past is the past. Miri will make friends at school, won’t she?”
“Oh, I’m sure of it. We are going to divide up each grade in the school to minimize the amount of conflict within any class. All the kids in the class will be friends.”
“Daddy, that makes no sense at all.”
“Why not, Bethie?”
“Well, to minimize conflict in classes, you will have to sacrifice something else, won’t you? What about the chances a person has of making a good friend? Is Miri really going to be in a class of people who will be her friends, or will she just be in a class of people who won’t be her enemies.”
“Uh-oh. I guess I should have talked to you about this first, right?”
“Always wise, Daddy. Always wise.”
“OK, suppose I abandon conflict avoidance as a parameter, and only seek friends to maximize friendship.”
“What do you mean by maximizing friendship?”
“Well, Bethie, it’s obvious, isn’t it? Each person should have as many friends in the room as possible.”
“As many weak friendships as possible? Or do you think Miri would want a few close friendships.”
“Of course she would want close friends. I see it now, that’s obviously what she wants. I suppose I should arrange for each person to have few strong friendships even if I have to let the rest of the class be very weak ones.”
“I don’t think you have a very good grasp of the situation, Daddy, if you’ll pardon me for saying so. Suppose you had a knob labelled minimum level of friendship anywhere, and a meter labelled maximum level of friendship for each individual. Got that?”
“OK. Now let me think this through. If turn the knob to allow lower levels of friendship overall, the maximum levels for each person has got to rise.”
“Right. Now allow even lower levels overall. When do you get the maximum compatibility per person?”
“Um, that would be low, below zero, actually. Meaning we might permit some hostility into the class, if necessary to everyone a closer friends. But that wouldn’t be good, would it? It’s almost the opposite of what we started out with.”
“Who told you it was best to minimize conflict, Daddy?”
“I see. Is she a young child about to enter a school classroom for the first time? Or is she a teacher, who worries about having to keep order in a class of kids who don’t get along?”
“Oh, Beth, not only did I fail to think Miri needs friends, I also forgot to ask her what kind of class she’d like to be in. Instead I asked a teacher what kind of class she’d want to teach.”
“It’s not too late, Daddy. I’m sure Miri is easy to find, probably in her room.”
Indeed she was.
“Miri, Beth tells me that I’ve been an idiot, again. She said it’s not enough to agree to put you in a class of kids your own age, I should ask you what kind of class that should be.”
“Do you mind if I prompt you, Miri? Daddy seems to need a bit of help sometimes.”
“Oh, Beth, thank you. I’ve been so worried. What should I ask?”
“Well, let me tell you his first version. He asked Annette, who is a teacher, and a little biased towards classes she’d like to teach. She described a class with almost no disagreements at all, everybody liking each other a little bit, but no real friendships. Is that what you want.”
“Oh, no, no Uncle Ken. Please put me in a class with a real friend. I don’t care about the other kids as long as I have one friend.”
“I’m sorry, Miri. I just didn’t think.”
“OK, good, Daddy, now we have Miri’s view on one thing. Let’s try another one. Miri, suppose Daddy arranged for you to have one pretty good friend, not the best possible, but pretty good, just to make sure the rest of the class got along. Would that be OK?”
“Um, I guess. I guess it is nice if the rest of the class is sorta friendly, but I’d really like one best friend in the whole school, one just one pretty good friend.”
“Suspicions confirmed. Daddy, you may look sheepish now, if it will help. Now Miri, suppose that to make sure you get the best possible friend, we had to let a little conflict into the class. What if there was someone who didn’t like you? Or someone you didn’t like?”
“Well, well, uh, that’s would be too bad, but I could ignore him, uh, or her, couldn’t I, couldn’t I just be friends with my friend and don’t worry about anyone else?”
“Is that what you’d really like, dear?”, Ken asked looking not sheepish but sad.
“Please, Uncle Ken, please. I just want one friend, just one, I don’t care about the other kids in the class, I just want a friend. It’s what I dream about.”
“Oh, Miri, Miri, dear, I’m so ashamed. I wish you’d told me, but it’s my fault, I should have asked you. I’ve neglected you terribly. Oh, Miri, I’ve loved you so much, not just from when you came to me, but since you were born. And now I’ve treated you so badly. Please forgive me.”
“It’s not your fault, Uncle Ken, it’s not. You know, um, well, I wasn’t always so shy, but, well now I am, and I just couldn’t tell you what I wanted. I was afraid.”
“Oh, Miri, never be afraid to tell me anything or ask for anything. I will always do whatever I can for you. Always. I’ve just been so blind.”
Ken and Miri were both crying. Beth quietly slipped through the door and left them to grow closer again.
Some further details of how this was implemented:
The children were given questionnaires and personal interviews, after which their interpersonal compatibility was estimated. The result was a weight matrix, which 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.
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.
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 Sony 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.