MHB Solve 17 Difficult Math Problems: Proving At Least 2 Committees are Identical

[yakin]

There are 4 people in a class. Among them, they are to solve 17 difficult math problems.

They form 17 committees – one committee to deal with each of the 17 problems.

Prove that at least 2 of these committees contain exactly the same people.

PLEASE EXPLAIN HOW EACH STEP TO REACH TO THE CONCLUSION.
THANKS!

 

[Evgeny.Makarov]

How many groups can be formed from these four people? Hint: Obviously, each person can belong or not belong to a group. Then use the rule of product to count the number of ways to include/exclude all four people.

 

[soroban]

Hello, yakin!

There are 4 people in a class. Among them,
they are to solve 17 difficult math problems.

They form 17 committees – one committee
to deal with each of the 17 problems.

Prove that at least 2 of these committees
contain exactly the same people.

With 4 people, there are only 15 possible committees.

. . \begin{array}{ccccc} 1&A&B&C&D \\ 2&A&B&C&- \\ 3&A&B&-&D \\ 4&A&B&-&- \\ 5&A&-&C&D \\ 6&A&-&C&- \\ 7&A&-&-&D \\ 8&A&-&-&- \\ 9&-&B&C&D \\ 10&-&B&C&- \\ 11&-&B&-&D \\ 12&-&B&-&- \\ 13&-&-&C&D \\ 14&-&-&C&- \\ 15&-&-&-&D \\ \cancel{16}&-&-&-&- \end{array}

Therefore, at least two of the 17 committees
. . must contain exactly the same people.

 

[Deveno]

This is how I look at it: suppose we want to make as many different committees as possible.

We have 4 possibilities: a committee may contain 1,2,3, or 4 people.

There is only ONE way to make a committee of 4: all the students belong to it.

There are 4 ways to make a committee of one, one way for each student.

There are 4 ways to make a committee of 3 (since that amounts to choosing "who to leave out").

So we are left with the final possibility of how many ways we can choose a committee of 2 students. This is given by "4 choose 2" or:

$\dfrac{4!}{2!(4-2)!} = \dfrac{24}{2\ast2} = \dfrac{24}{4} = 6$.

Adding up these possibilities we get:

1+4+4+6 = 15 possible DIFFERENT committees.

Since we must choose 17 committees, 2 of these must match (individually) one of the 15 possible (although more matches might actually occur).

 

[soroban]

Another way to count the possible cases . . .

There are four people available.

For each person, we have two choices:
. . (1) Yes (on the committee),
. . (2) No (not on the committee).

Hence, there are: 2^4 \,=\,16 possible choices.

But this list includes No-No-No-No
. . (no one is on the committee).

Therefore, there are 15 possible committees.