Math 386: Combinatorics Announcements

Test I

 	A       B       C       D       F
	70-100	53-69	34-52	26-33	0-25
 

Test II

	A       B       C       D       F
	79-100	62-78	45-61	38-44	0-37

Test III

	A       B       C       D       F
	86-100	75-85	64-74	56-63	0-55

Final Exam

	A       B       C       D       F
	115-150	95-114	75-94	64-74	0-63

The Seating Problems

For these problems we assume that there are 9 people in the class (including the teacher) and 28 seats (including the ``head chair'' at the teacher's desk).

• Problem A1. How many seating arrangements are there for the 9 people in the 28 chairs? (It matters which person sits in which chair,not only which chairs are used.)
• Problem A2. The same, if the teacher doesn't sit in the head chair.

The Committee Problems

For these problems we assume there are 9 people in the class, except where I specify different numbers. We want to form various committees (attendance committee, party committee, grading committee, etc.) using these people, subject to certain rules.

• Problem A3. 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.

  N.B. We decided after some discussion that there should always be a Rule 0.

  • Rule 0. Every committee has at least one member.
• Problem A4. What is the maximum possible number of committees, given Rules 0-2?
• Problem A5. What is the minimum possible number of committees?

After looking at some answers to Problem A3 that gave us some ideas about Problems A4 and A5, we decided that there were some trivial solutions that we should rule out. So we made up

• Rule 3. Every committee has more than one person.
• Rule 4. The Committee of the Whole is not allowed.
• Problems A3', A4', A5'. Solve Problems A3-A5 with Rules 3 and 4 added.
• Problem A6. Solve Problem A3 with Rules 0-2 and exactly 3 people on each committee. Try it with (a) 9 people. (This is not at all trivial! But solvable.) (b) 8 people. (c) 7 people. (d) 4 people.
  

  This led to an interesting solution that was overly simple-minded although not trivial. For example, all but one person form a committee, and that last person forms a separate committee with each other person. So I set forth:

  • Rule 5. There exist 4 people, no 3 of whom are on a committee together.

  But even with this, there were simple-minded solutions like: all but 2 people form one committee, and (you fill in the details). So I gave the Big Rule that makes what we call ``projective geometry'':

  • Rule 2'. Every pair of committees has exactly one member in common.
• Problem A7. Do there exist committees satisfying Rules 0-4 and 2'? Parts (a)-(d) as in Problem A6. (Each part is a different problem. The level of difficulty, as well as the answers, might be very different.)
• Problem A8. Do there exist committees satisfying Rules 0-5 and 2'? Try it with 9 people, also with 7 people, and then with 8 people. Parts (a)-(d) as in Problem A6.

• 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.)