Math 386: Combinatorics Announcements

Test I

 	A       B       C       D       F
	76-100	60-75	41-59	32-40	0-31
 

Test II

	A       B       C       D       F
	82-100	62-81	42-61	32-41	0-31

Test III

	A       B       C       D       F
	75-100	58-74	41-57	32-40	0-31

Final Exam

The Committee Problems

For these problems we assume there are n people in the class, where n = 15 or 3 or 4 or 5 or 7. We want to form various committees (attendance committee, party committee, grading committee, etc.) using these people, subject to certain rules.

• Problem A1. Suppose we have only Rules 1 and 2. Is it possible to form a system of committees at all, ignoring how many committees there are?
  • Rule 1. Everyone is on a committee.
  • Rule 2. Every 2 people are together on exactly one committee.
• Problem A2. What is the minimum possible number of committees?
• Problem A3. What is the maximum possible number of committees?

  After looking at some answers to Problem A1 that gave us some ideas about Problems A2 and A3, it seemed that there were some trivial solutions that we should rule out. So I added

  • Rule 3. The Committee of the Whole is not allowed.
  I also added a fundamental new rule:
  • Rule 4. Every pair of committees has exactly one member in common.
• Problems A1', A2', A3'. Solve Problems A1-A3 with Rules 3 and 4 added.

  This led to interesting solutions. For example, all but one person form a committee, and that last person forms a separate committee with each other person. For another example, every pair of people form a committee. (We also noticed that Rule 4 prevents a committee with no members. Furthermore, due to Rule 4 it was impossible to add to the two solutions mentioned any committees with only one member.)

• In Theorem 5.7.2, first paragraph of proof, the s's should be m's.
• In properties 1 and 2 at the top of p. 152, each of the first two A's should be X. (The A⁺ and A^- and the last A are correct.)