An island has 50 clubs. Each inhabitant of the island is a member of 1 or 2 clubs. Each club has at most 55 members, and for every pair of clubs, there is an inhabitant of the island who is a member of both clubs. Find all possible values for the number of inhabitants of the island. Justify your answer.
Solution

There are $\binom{50}{2}=1225$ pairs of clubs and for each of them, we must have one inhabitant who belongs to both. Let's denote these inhabitants by $H_{i j}$ with $i, j \in\{1,2, \ldots, 50\}$ and $i<j$. If two of them are equal, one inhabitant would be in three clubs, which would be a contradiction. Therefore, all the inhabitants $H_{i j}$ are distinct, showing that the island needs to have at least 1225 people and that each club has at least one inhabitant of the form $H_{i j}$. Fixing any club, it has 49 distinct inhabitants in common with the other 49 clubs. Since it can have at most 55 inhabitants, it will contain at most 6 that are not of the form $H_{i j}$. Thus, the maximum number of inhabitants on the island is $1225+50 \cdot 6=1525$. Now consider an integer $n \in[1225,1525]$ and 1225 distinct people. Associate a label $H_{i j}$, with $i, j \in\{1,2, \ldots, 50\}$ and $i<j$, to each one, and place the person with the label indexed by $i$ in the club $C_{i}$. These will be the only people in two clubs. Since $n-1225 \leq 300$, we can distribute the remaining people by inserting them into groups of up to 6 people in the $55-49=6$ empty positions of each of these 50 clubs created. They will be the only people who will participate in only one club. We can conclude that the set of possible values is the interval of integers $[1225,1525]$.