A photographer must take photos of a party with 10 members of the same family. Each of the 45 possible pairs of people in this family must appear together in exactly one photo. Additionally, there are only two types of photos: those with 2 or 3 people.

a) Verify that each person in the family must appear in at least one photo with only 2 people.

b) Verify that the photographer must take at least 19 photos.

c) Provide an example of a distribution of people in 19 photos that satisfies the given conditions.
Solution

a) Each person must appear with 9 other family members exactly once in some photo. In photos with 3 people, one person appears in exactly 2 pairs, and since 9 is odd, it is necessary that each person appears in at least one photo with exactly 2 people.

b) Let $x$ be the number of photos with 3 people and $y$ be the number of photos with 2 people. We want to estimate the total number of photos, which is given by $x+y$. In each photo with 3 people, there are 3 pairs of family members, and in each photo with 2 people, there is only one pair. Therefore,

$$
3 x+y=45
$$

From the previous item, since each person must appear in at least one photo with 2 people, we must have $y \geq 5$. Consequently, $x=(45-y) / 3 \leq 13$. Thus, we have:

$$
\begin{aligned}
x & \leq 13 \\
-x & \geq-13 \\
-2 x & \geq-26 \\
45-2 x & \geq 19 \\
x+y & \geq 19
\end{aligned}
$$

c) Therefore, we must have at least 19 photos. To construct an example with exactly 19 photos, name the 10 family members by the numbers $0,1, \ldots, 9$. We will start constructing the example by forming 4 photos of 3 people: $(1,2,3),(3,4,5),(5,6,7)$, and $(7,8,1)$. In the diagram below, each triangle represents a photo.

![](https://cdn.mathpix.com/cropped/2024_05_01_96f63abf6bdef97495eag-26.jpg?height=470&width=465&top_left_y=505&top_left_x=677)

To choose the next photos, we will include the relative numbered $0$ and use pairs of relatives that have not yet appeared in any photo. For example, choose the following group of 4 photos of 3 people: $(0,1,4),(0,8,5),(0,2,7)$, and $(0,3,6)$. In the next diagram, these photos are represented by triangles with dashed lines.

![](https://cdn.mathpix.com/cropped/2024_05_01_96f63abf6bdef97495eag-26.jpg?height=473&width=465&top_left_y=1307&top_left_x=677)

Note that in this diagram, there are still pairs of family members who have not appeared in any photo, such as the relatives 1 and 6. Now, let's include the person numbered 9 and form the following groups of 4 photos of 3 people: $(9,1,6),(9,2,5),(9,3,8)$, and $(9,4,7)$. See that in these photos, all people from 1 to 8 appear with 0 and 9 in some photo. Among the people from 1 to 8, some pairs of family members still have not appeared in photos. To finish, consider the following configuration with one more photo of 3 people and 6 photos of 2 people:

$$
(2,4,6),(2,8),(6,8),(0,9),(1,5),(3,7) \text { and }(4,8)
$$