Deranging groups

Ok so this is a mathematical problem. I plan to give three group assignments to my IIMB class. Let’s assume that there are 60 kids and for each assignment I want them to form groups of four members each. For the first assignment I’ve let them form the groups themselves.

For the second assignment, though, I want to create a “derangement” of these groups – in the sense that I want to form a different set of 15 groups of 4 members each such that no pair of students who are in the same group for assignment 1 will be in the same group for assignment 2. And I’m looking for an algorithm to thus “derange” my students. And whether it is possible at all to derange students thus.

My inclination is that this might have a solution in graph theory – in terms of graph colouring or something? Take the students from the first group and join every pair of students that are in the same group with an edge. Then colour the nodes of the graph. Pick nodes of the same colour (these are students that haven’t been in groups together) and randomly assign them to new groups. Repeat for all colours.

Question is how many colours we need to colour the graph. If it’s planar, we’ll need only 4 colours! And considering that the first assignment has 4 students per group, the maximum degree of a node is 3. If the maximum degree of an edge is 3, does that say anything about the planarity of the graph? If I derange the students once for assignment 2, can I do it again for assignment 3 (now each node has a degree of 6!) ? How do I think about this mathematically? Can you help?

One thought on “Deranging groups”

  1. Why not the following trivial algo: Each student has a label according from 0 – 14, depending on the first group. Now create groups by sequentially going through labels modulo 16 (so grp 1 is 1,2,3,4, with an arbitrary student from each of the old groups; grp 2 is 5,6,7,8, and so on). Doesn’t this give a derangement (actually many derangements…), or am I missing something?

Put Comment