Grouping question (not sure what branch of math this is!)

[sivodsi]

Hi there,
I have a real world grouping problem here, and I would be exceedingly grateful for any help I can get!

I'm a researcher in the field of applied linguistics who is investigating the language and interaction of students when they are in groups of varying sizes - specifically, in pairs, threes or fours.

I plan to run an experiment in which a class of 24 students will do a discussion with different partners each time, once in a pair, once in a group of 3, and again as a group of 4.

The other restriction is that due to avoid a 'warm-up' effect (practice improves ability), some should do it first in a pair, three and four (i.e. they should not all do it in pairs first, or all in groups of three or four first).

I have tried to work it out just by sorting students into groups and can show the best I have done so far, after a few mind numbing hours.

In the table below I've let each person be represented by a letter, from A - X (24 students)

Group of	First Round	Second Round	Third Round
two	AB CD EF GH IJ	KO MX SV WR TU	LN PQ
three	KLM NOP	ACQ EGJ	BSX DRV FWT HIU
four	QRST UVWX	BDHL FINP	AKGM CEJO

You can see above that K and M are together in a group of three in the first round and then again in the third round, and E and J are together in the second and again the third. Every time I make a change to put these guys with somebody new each time, I create another combination who have the same partners in a different group!

My questions are:
1) am I doing the impossible here? I kind of think that it is not possible to have zero same partners with the number of 24, but would be happy to hear from a mathematician if there is some proof of this.

2) if it is impossible with a group of 24, with what number(s) is it possible?

Really looking forward to help on this one, much thanks in advance if you can supply an answer!:grin:

 

[daon2]

There looks to be an awful lot of changing going on each round, so it is nasty to generalize.

Let \(\displaystyle a_1,a_2,a_3\) be the number of groups of size 2 on rounds 1,2,3 respectively.
Let \(\displaystyle b_1,b_2,b_3\) be the number of groups of size 3.
Let \(\displaystyle c_1,c_2,c_3\) be the number of groups of size 4.

In each case we have \(\displaystyle 2a_i+3b_i+4c_i=24\).

There are \(\displaystyle N_{a1}=\dfrac{{24\choose 2}{22\choose 2}\cdots {24-2(a_1+1)\choose 2}}{a_1!}\) ways to pick the people in the two-group size. \(\displaystyle N_{b1}\) comes next. \(\displaystyle N_{b1} = \dfrac{{24-2a_1\choose 3}{24-2a_1-3\choose 3}\cdots {24-2a_1-3(b_1+1)\choose 3}}{b_1!}\). And similarly for \(\displaystyle N_{c1}\).


Now for \(\displaystyle N_{a2}\). The members of the two-group size in round two come from the three and four group sizes. So we have \(\displaystyle 3b_1+4c_1\) to pick from. Hence \(\displaystyle N_{a2} = \dfrac{{3b_1+4c_1\choose 2}{3b_1+4c_1-2\choose 2}\cdots {3b_1+4c_1-2(a_2+1)\choose 2}}{a_2!}\). And \(\displaystyle N_{b2} = \dfrac{{2a_1+4c_1-2a_2\choose 3}{3b_1+4c_1-2a_2-3\choose 3}\cdots {3(b_1-b_2+1)+4c_1-2a_2\choose 3}}{b_2!}\).

And similarly for the (uglier) third grouping case.

What you are interested in are numbers \(\displaystyle a_i,b_i,c_i\) that give you nonzero outcomes for each \(\displaystyle N_{ji}\), in which case there is a solution. If you find some that give a solution, then making choices as per the formula will result in an answer for your problem.

 

[sivodsi]

Thanks for answer!

I am not a mathematician, so it will be some time before I can digest your suggestion...

This particular field is quite relevant to a few similar problems I face. Is there any text book you recommend for background reading?

Fortunately I have plenty of time before I need to put this plan into action (March next year!).

 

[sivodsi]

Actually, even without investigating the math of this, I'm almost certain that there is no solution.

That is, I don't think its possible to have each member participate in a different group without at least one group repeating partners. The reason is that the groups of 3 or 4 create bottlenecks which can't be beaten.

For example, in the groups arrangement I gave earlier, the K and M double up can be solved by swapping M and B in the first round, but no matter how I swap E and J in the second round, there always remains somebody who will have the same partner in the third round.

Can anyone prove me wrong?