14
$\begingroup$

The proposed problem was the following (translated into English by me):

"A school has $16$ students interested in participating in a team competition. First, they must split themselves into $8$ pairs. Then, each of those pairs must choose (among themselves) someone to be their leader. Finally, two teams of $8$ students are formed by choosing $4$ pairs to compose the first team, which already locks the opposing team.

Considering two teams to be equal if, and only if, they are composed of the same pairs (with pairs being equal if they are composed of the same students, with the same leader), in how many distinct ways can these $16$ students divide themselves into two teams of eight?"


Solution Provided (translated by me):

First, compute the total amount of distinct pairs that can exist. This is clearly given by $C_{16,2} = \frac{16!}{14!2!} = 15\cdot8$. Since each pair has two choices of leader, we also multiply by two, to obtain $16\cdot15 = 240$

Now, multiply the amount of distinct pairs by the total number of ways of choosing $4$ out of the $8$ formed pairs to obtain the final answer:

$C_{8,4} \cdot 240 = \frac{8!}{4!4!} \cdot 240 = 70 \cdot 240 = 16800$


My issues:

I don't believe that using $C_{16,2}$ makes any sense, as (in my mind) after you choose the first pair, you cannot choose any other pair that contains either of the students in the first one you chose (and so on).

I also don't believe this number correctly represents the total amount of ways of forming 8 pairs under these conditions, which is the number that would make sense to use in place of $C_{16,2}$ (in my opinion).


My attempt:

We begin by computing the number of ways of constructing $8$ distinct pairs out of $16$ students.

For the first pair, we have $16 \choose 2$ possible ways. For the second pair, $14\choose 2$. And so on until the final pair which is $2 \choose 2$. So the total number of ways of assembling 8 pairs out of 16 students seems to be given by:

$\prod_{n=1}^{8}{2n \choose 2}$

Which works out quite nicely to $\frac{16!}{2^{8}}$

But this is not quite the number I am looking for yet. Since I don't actually care about the order of the pairs, I have to divide by $8!$, since when multiplying them out like I did above, I consider choosing some pair $A$ before some pair $B$ different then choosing first $B$ and then $A$, when it clearly is not.

So, the final number works out to: $\frac{16!}{8!2^{8}}$.

Like it was done in the official solution, I must now multiply by $2^{8}$, since each individual has two choices of leaders. This gives me the total number of ways of forming $8$ distinct pairs with leaders which is $\frac{16!}{8!}$

The conclusion is now the same as in the official solution: We now multiply by the amount of different ways of choosing $4$ out of the $8$ pairs. This gives:

$\frac{16!}{8!}\cdot C_{8,4} = \frac{16!}{8!}\cdot\frac{8!}{4!4!} = \frac{16!}{4!4!}$

And finally, we must divide by two since choosing, for example, pairs $A,B,C,D$ (out of pairs $A,B,C,D,E,F,G$) or choosing $D,E,F,G$ makes no difference on the resulting two teams.

So my final answer turns out to be $\frac{16!}{4!\cdot 4!\cdot 2}$, which is not even close to the number obtained in the official one.


The question: Which one (if any) is right, and why is the other one (or both) wrong?

$\endgroup$
2
  • 6
    $\begingroup$ Official solution incorrectly uses $C_{16,2}$ for pair formation. This ignores the restrictions that happen each time a pair is formed (reducing the pool of available people for the next pair). Also it multiplies by the number of pairs instead of using combinations. Using multiplication implies an order in the process of selecting the pairs for a specific team, which doesn't reflect the reality of how teams are formed in this scenario. So your solution is correct $\endgroup$
    – rumathe
    Commented Feb 17 at 16:51
  • 2
    $\begingroup$ @rumathe I agree with you, but that raises the question of what the correction solution is. I think mine is right, but considering the context this question comes from (an exam where you get maybe 2 minutes per question on average), the complexity makes me suspicious that it is not. $\endgroup$
    – Almeida
    Commented Feb 17 at 16:54

5 Answers 5

20
$\begingroup$

Your solution and answer look fine to me. Here's an alternate approach.

We line up the $16$ students. The first $8$ will form one team and the next eight another. In each team, the first two form one pair, the next two another, and so on. In each pair, first student is the leader.

Now, the $16$ students can be arranged in a row in $16!$ ways. But we don't care about the order of the $4$ pairs inside a team. So, divide by $4! \cdot 4!$ for the two teams. Also, the order of the teams doesn't matter. So divide by $2$.

So, the answer is $\dfrac{16!}{4! \cdot 4!\cdot 2}$

$\endgroup$
1
  • 1
    $\begingroup$ This... is way easier to explain. Thank you. $\endgroup$
    – Almeida
    Commented Feb 17 at 16:58
6
$\begingroup$

Arrange the Students in a line & Select them 2 at a time to make the Pairs , where the earlier Student is the leader.
This gives $16!$ ways to make the Student line.

We can re-order the Pairs like $A,B,C,D \equiv C,D,A,B$ , hence we have to reduce by $4!$ for the first team & reduce by $4!$ for the second team.
We can also reorder the 2 whole teams , hence we have to reduce by $2!$

We then get the total $16!/[4!4!2!] = 18162144000$ which matches what you got.
That is the Correct Answer.

The text book answer is wrong & too small & too much off-target.
The given argument is wrong too , due to issues listed by you & more !

$\endgroup$
3
  • $\begingroup$ "The text book answer is wrong & too large" Did you mean too small? $\endgroup$
    – Almeida
    Commented Feb 17 at 16:57
  • $\begingroup$ Thanks for the alternative solution, this approach is a lot easier to explain then the convoluted solution I came up with. Thanks a lot again! $\endgroup$
    – Almeida
    Commented Feb 17 at 16:59
  • $\begingroup$ Nice catch , @Almeida , I updated that line ! $\endgroup$
    – Prem
    Commented Feb 17 at 17:02
5
$\begingroup$

Another alternative approach.

There are

$$A = \binom{16}{8} \times \frac{1}{2}$$

ways of dividing the $~16~$ people into two groups of $~8,$ since selecting persons 1 through 8 is the same as selecting persons 9 through 16. An alternative (equivalent) computation for $~A~$ is

$$A = \binom{15}{7},$$

since there are $~\displaystyle \binom{15}{7}~$ ways of selecting the $~7~$ other people who will be on the same team as person-1.

Then, there are

$$B = \binom{8}{2} \times \binom{6}{2} \times \binom{4}{2} \times \binom{2}{2} \times \frac{1}{4!} = \frac{8!}{2^4 \times 4!}$$

ways of dividing one of the teams of $~8~$ people into $~4~$ pairs. The $~4!~$ factor in the denominator reflects that it is irrelevant in what order the pairs are constructed.

So, there are $~B^2~$ ways of dividing both groups of $~8~$ into $~4~$ pairs each.

Then, there are

$$C = 2^8$$

ways of choosing the pair leaders.

So, the final computation is

$$A \times B^2 \times C\\ = \frac{(16)!}{8! \,8!} \times \frac{1}{2} \times \left[ ~\frac{8!}{2^4 \times 4!} ~\right]^2 \times 2^8 \\ = \frac{(16)!}{4! \times 4! \times 2}.$$

$\endgroup$
5
$\begingroup$

${16 \choose 2}\times 2=240$ is the number of ways of choosing the first pair and its leader.

But having done that, the number of ways of choosing the second pair and its leader from the remaining students is ${14 \choose 2}\times 2$, and then ${12 \choose 2}\times 2$, and so on down to ${2 \choose 2}\times 2$ for the last pair and its leader. The provided solution seems to have ignored these, so is wrong by a multiplicative factor equal their product, which is $14!$.

It has also ignored the overcounting by a factor of $8!$ as different orderings of pair selections will give the same eight pairs.

The proposed solution is correct to say that there are ${8\choose 4}$ ways of choosing four out of eight pairs for the first team.

But it seems to have ignored the possibility that the other four pairs are chosen for the first team instead. So if you want to take account of this (it is not clear from the wording of the question whether the first team and the second team should be distinguished), you might say this double counting should be taking into account with a multiplicative factor of $\frac12$.

This reconciles the proposed solution and your answer:

$$16800 \times 14! \times \frac{1}{8!} \times \frac12 = 18162144000=\frac{16!}{4!\cdot 4!\cdot 2}.$$

$\endgroup$
1
  • $\begingroup$ +1 for a clear explanation. $\endgroup$ Commented Feb 19 at 22:00
0
$\begingroup$

We all agree that the provided answer is incorrect for the reasons you state and others. Then the fun starts. Here is how I see it:

First, choose the leaders, eight out of 16 students C(16,8) ways.

Then assign a partner for each leader from the remaining 8 students 8! ways.

Finally, choose team A from the eight pairs C(8,4) ways. Team B will be composed of those not chosen for A.

So the total is C(16,8) 8! C(8,4),

= 16! / 4! 4! = 1,307,674,368,000, if I worked my calculator right.

Assuming that teams A and B are distinctly identifiable. (Otherwise, it's half that number).

Am I missing something?

$\endgroup$

You must log in to answer this question.

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