Let us discuss an interesting combinatory problem. Here is the question.
A local high school math club has 12 students in it. Each week, 6 of the students go on a field trip.
(a) Jeffrey, a student in the math club, has been on a trip with each other student in the math club. Determine the minimum number of trips that Jeffrey could have gone on.
(b) If each pair of students have been on at least one field trip together, determine the minimum number of field trips that could have happened.
Any clue on how to work with this problem?
Firstly, this is a combinatorial problem. The questions are looking for a number — a naive way is to make a schedule and count for the number.
However if we arbitrarily make a schedule, even in the best effort, can we guarantee that the minimum number of trips is reached in our scheduling (both for Jeffery, and for the total number of trips). No. The minimum can not be reached that easily.
A better way is to show there is a minimum n; for less than n trips, the restricting condition becomes impossible. Take the case for Jeffery (referring to question (a)). Suppose Jeffery has been in two trips. In the first trip, he was with five students A1, A2, A3, A4, A5; in his second trip, he was with B1, B2, B3, B4, B5 (assume only Jeffery took both these trips). Concludingly, he has been with ten other students. Adding himself, we counted 11 students. But recall there are 12 students, so there is a C who has not been in any of these two Jefferey’s trips. Therefore, 3 is the minimum number of trips if, Jeffery has been together with any of the other 11 students for at least one trip – 3rd trip is necessary for Jeffery to be with C together
The question (b) has a more involved nature. First point to consider: in what way can count to ensure any two students have been together in at least one field trip? Arguing for the minimum, we know too less trips will not generate an arrangement ensuring the condition: any two students are together at least once; however, if we do reach the minimum number of trips, would that condition be satisfied? — that is the second point to consider. If we want to guarantee the condition satisfied, then the obvious way is to actually make a schedule so as to check that condition — in this example, we need to show that in some n trips, any two of the 12 students have been in a field trip together. So the clues are provided for your — dear reader; would you like to carry it further?
We leave to our readers to complete this question. ** Reference solutions will be posted soon. **