Problem (Combinatorics):
Eight students attend a Harper Valley ARML practice. At the end of the practice, they decide to take selfies to celebrate the event. Each selfie will have either two or three students in the picture. Compute the minimum number of selfies so that each pair of the eight students appears in exactly one selfie.

Solution:
The answer is 12 . To give an example in which 12 selfies is possible, consider regular octagon $P_{1} P_{2} P_{3} P_{4} P_{5} P_{6} P_{7} P_{8}$. Each vertex of the octagon represents a student and each of the diagonals and sides of the octagon represents a pair of students. Construct eight triangles $P_{1} P_{2} P_{4}, P_{2} P_{3} P_{5}, P_{3} P_{4} P_{6}, \ldots, P_{8} P_{1} P_{3}$. Each of the segments in the forms of $\overline{P_{i} P_{i+1}}, \overline{P_{i} P_{i+2}}, \overline{P_{i} P_{i+3}}$ appears exactly once in these eight triangles. Taking 8 three-person selfies (namely $\left.\left\{P_{1}, P_{2}, P_{4}\right\},\left\{P_{2}, P_{3}, P_{5}\right\}, \ldots,\left\{P_{8}, P_{1}, P_{3}\right\}\right)$ and 4 two-person selfies (namely $\left.\left\{P_{1}, P_{5}\right\},\left\{P_{2}, P_{6}\right\},\left\{P_{3}, P_{7}\right\},\left\{P_{4}, P_{8}\right\}\right)$ gives a total of 12 selfies, completing the desired task.

A diagram of this construction is shown below. Each of the eight triangles is a different color, and each of the two-person selfies is represented by a dotted diameter.



It remains to show fewer than 12 selfies is impossible. Assume that the students took $x$ three-person selfies and $y$ two-person selfies. Each three-person selfie counts 3 pairs of student appearances (in a selfie), and each two-person selfie counts 1 pair of student appearances (in a selfie). Together, these selfies count $3 x+y$ pairs of student appearances. There are $\left(\begin{array}{l}8 \\ 2\end{array}\right)=28$ pairs of student appearances. Hence $3 x+y=28$. The number of



selfies is $x+y=28-2 x$, so it is enough to show that $x \leq 8$.

Assume for contradiction there are $x \geq 9$ three-person selfies; then there are at least $3 \cdot 9=27$ (individual) student appearances on these selfies. Because there are 8 students, some student $s_{1}$ had at least $\lceil 27 / 8\rceil$ appearances; that is, $s_{1}$ appeared in at least 4 of these three-person selfies. There are $2 \cdot 4=8$ (individual) student appearances other than $s_{1}$ on these 4 selfies. Because there are only 7 students besides $s_{1}$, some other student $s_{2}$ had at least $[8 / 7\rceil$ (individual) appearances on these 4 selfies; that is, $s_{2}$ appeared (with $s_{1}$ ) in at least 2 of these 4 three-person selfies, violating the condition that each pair of the students appears in exactly one selfie. Thus the answer is $\mathbf{1 2}$.

Final answer: 12