At a track meet, every group of $n$ participants shares exactly one common friend. Suppose runner $P$ has the largest number of friends. Determine how many friends $P$ has.
Assume for this question:
- $n \in N$ such that $n ≥ 3$
- Friends are mutual, EX: if $X$ is friends with $Y$, then $Y$ is friends with $X$
- No one is friends with themselves
- a group of runners has a "common friend" $a$ iff each runner in the group is friends with $a$
Prove the answer.
Update for Clarification
- $n$ is the size of the group, not the total number of attendees.
- There are an arbitrary number of groups
- The answer should be expressed in terms of $n$
- If $X$ is friends with $Y$ then both $X$ and $Y$ are at the trackmeet
- Assume there are at least $n + 1$ attendees.
Thank you very much for your effort so far @fleablood
P can't like as many as n people.
Label n of P's friends as $a_1,... a_n$.
$(P, a_1, ...., a_{n-1})$ have P as the mutual friend. So $(a_1,..., a_{n-1})$ have no mutual friend. So $(a_1, ..., a_n)$ have $a_n$ as a mutual friend. So $(P, a_2, ...., a_n)$ have both P and $a_n$ as mutual friends. Impossible.
So P has n-1 friends or fewer.
But as any group of n people have 1 mutual friend, that mutual friend has at least n-1 friends. So P has at least n-1 friends.
So P has n-1 friends.