2
$\begingroup$

A class of 96 students must divide itself into 24 sets of 4 for an assignment. However, during the year there are 4 such assignments, and no student can ever work with any of the same partners. Prove that this is possible or impossible to do.

Note that, if for project 1, Anne, Bob, Chris, and David are working together, then for project 2 Anne cannot work with Bob, Chris, or David for any other project.

$\endgroup$
4
  • 1
    $\begingroup$ What have you tried? $\endgroup$
    – Bergson
    Nov 2, 2018 at 19:58
  • $\begingroup$ @ThomasBladt For each person, they must find 3 other partners to form a set. There are "95 choose 3" ways that they can do this. However many of these groups have overlapping members. I am not sure how to proceed. $\endgroup$ Nov 2, 2018 at 22:32
  • $\begingroup$ Also, I don't know if this makes a difference to you, but this is not a question given to me for homework (so I'm not trying to ask you to do my homework). This is a situation that is actually happening in one of my classes. I feel confident that it is possible, but I dont know how to prove it (and of course I am not 100% certain that it is possible). I do have a math background though, so please feel free to use formal mathematics in your explanation. $\endgroup$ Nov 2, 2018 at 22:34
  • $\begingroup$ I think it's probably possible. I wrote a script to try to construct an example in a very simple-minded way. I got $24$ teams for each of the first two projects, $22$ for the third and $23$ for the fourth. If such a simple-minded, greedy approach came so close, I strongly suspect that something more sophisticated would succeed. The thing that occurs to me is a commercial-grade SAT solver, but I don't have access to one. $\endgroup$
    – saulspatz
    Nov 2, 2018 at 23:44

1 Answer 1

6
$\begingroup$

I can't come up with a combinatorial argument for the general case, but we can construct an example (and hence proving it is possible) as follows:

We label each student as $s_i$ for $i \in\{1,2,\ldots,96 \}.$ The first time we assign the groups as follows:

$$\begin{bmatrix}s_1& s_2& s_3 & s_4 & s_5 & s_6 &\cdots& s_{22} & s_{23} & s_{24}\\ s_{25}& s_{26}& s_{27} & s_{28} & s_{29} & s_{30} &\cdots& s_{46} & s_{47} & s_{48} \\ s_{49}& s_{50}& s_{51} & s_{52} & s_{53} & s_{54} &\cdots& s_{70} & s_{71} & s_{72}\\ s_{73}& s_{74}& s_{75} & s_{76} & s_{77} & s_{78} &\cdots& s_{94} & s_{95} & s_{96} \end{bmatrix} \tag{1}$$ where each column represents a group. Notice that there are $24$ groups, with $4$ students in each one. Now, for the second time, we proceed as follows: we leave the first row as it is, we shift the second row one place to the right, the third row two places to the right and the fourth row three places to the right, so we end up with $$\begin{bmatrix} s_1& s_2& s_3 & s_4 & s_5 & s_6 &\cdots& s_{22} & s_{23} & s_{24} \\ s_{48}& s_{25}& s_{26} & s_{27} & s_{28} & s_{29} &\cdots& s_{45} & s_{46} & s_{47} \\ s_{71}& s_{72}& s_{49} & s_{50} & s_{51} & s_{52} &\cdots& s_{68} & s_{69} & s_{70} \\ s_{94}& s_{95}& s_{96} & s_{73} & s_{74} & s_{75} &\cdots& s_{91} & s_{92} & s_{93} \end{bmatrix} \tag{2}$$

Starting from $(2)$, we do the same for the third assignment:

$$\begin{bmatrix} s_1& s_2& s_3 & s_4 & s_5 & s_6 &\cdots& s_{22} & s_{23} & s_{24} \\ s_{47}& s_{48}& s_{25} & s_{26} & s_{27} & s_{28} &\cdots& s_{44} & s_{45} & s_{46} \\ s_{69}& s_{70}& s_{71} & s_{72} & s_{49} & s_{50} &\cdots& s_{66} & s_{67} & s_{68} \\ s_{91}& s_{92}& s_{93} & s_{94} & s_{95} & s_{96} &\cdots& s_{88} & s_{89} & s_{90} \end{bmatrix} \tag{3}$$

and the fourth: $$\begin{bmatrix} s_1& s_2& s_3 & s_4 & s_5 & s_6 &\cdots& s_{22} & s_{23} & s_{24} \\ s_{46}& s_{47}& s_{48} & s_{25} & s_{26} & s_{27} &\cdots& s_{43} & s_{44} & s_{45} \\ s_{67}& s_{68}& s_{69} & s_{70} & s_{71} & s_{72} &\cdots& s_{64} & s_{65} & s_{66} \\ s_{88}& s_{89}& s_{90} & s_{91} & s_{92} & s_{93} &\cdots& s_{85} & s_{86} & s_{87} \end{bmatrix} \tag{4}$$

This ensures that each of the $4$ times no student meets with another previously met student. We can also see that there is more than one solution to this problem.

$\endgroup$
1
  • 2
    $\begingroup$ Slick. We can do this $4$ more times and get $8$ projects, but the method doesn't yield a ninth. I wonder what the maximum number of projects is. $\endgroup$
    – saulspatz
    Nov 3, 2018 at 1:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .