3. 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.
Solution:
(a) There are 11 students in the club other than Jeffrey and each field trip that Jeffrey is on has 5 other students. In order for Jeffrey to go on a field trip with each other student, he must go on at least $\left\lceil\frac{11}{5}\right\rceil=\lceil 2.2\rceil=3$ field trips .
To see that 3 trips is sufficient, we let the other students be $\left\{s_{1}, s_{2}, \ldots, s_{11}\right\}$. On the first trip, Jeffrey can go with $\left\{s_{1}, \ldots, s_{5}\right\}$, on the second trip with $\left\{s_{6}, \ldots, s_{10}\right\}$ and on the third trip with $s_{11}$ and any other 4 students. .
(b) From part (a), we know that each student must go on at least 3 trips. Since there are 12 students in total, if we count the number of trips that each student went on, we would get a minimum of $12 \times 3=36$. Since 6 students attend each field trip, that means there must be at least $\frac{36}{6}=6$ trips.
We now show that it is possible to do this with exactly 6 trips. Divide the students into 4 groups of 3 students each (groups A, B, C, D). There are 6 different pairs of groups $(\mathrm{AB}, \mathrm{AC}, \mathrm{AD}, \mathrm{BC}, \mathrm{BD}, \mathrm{CD})$. Let these pairs of groups be our 6 field trips. We see that since each group goes on a trip with each other group, that each pair of students goes on a trip together. Hence, this can be done with 6 trips.