1

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

Kyle Bustler
  • 19
  • 2
    This question appeared a day ago, http://math.stackexchange.com/questions/1472289/mutual-friends-at-a-game. Is it part of a contest? – lulu Oct 10 '15 at 18:03
  • No points challenge problem in my high school class. Thanks for pointing me to the duplicate. :) – Kyle Bustler Oct 10 '15 at 18:07
  • Is it part of the assumptions of the question that if X is friends with Y, then X and Y are both at the track meet? – ZKe Oct 11 '15 at 00:29
  • A solution is the tournament with n+1 people where they are all friends. But it seems a far more interesting problem to show that this is the only solution, or rather that other solutions also yield n as the maximum number of friends a runner can have. – ZKe Oct 11 '15 at 00:43
  • @Zackkenyon Yes, if they're friends both are at the track meet. That is exactly what we're trying to prove. I apologize if the question was ambiguous. – Kyle Bustler Oct 11 '15 at 16:51

1 Answers1

-1

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.

fleablood
  • 124,253
  • 1
    The claim "$(P, a_1, \ldots, a_{n-1})$ have $P$ as the mutual friend" contradicts the assumption that nobody is friends with themselves. – Gregory J. Puleo Oct 10 '15 at 22:24
  • No it doesn't. The mutual friend is the guy who is friends with all the people except themself. Thus the mutual friend is P. If I used your definition then there'd be no common friends as no-one is friends with themselves. Or is your issue with common vs. mutual? I took those to be the same. I'll edit to "common". – fleablood Oct 10 '15 at 22:32
  • Oh, I see what you are saying. Dang it. – fleablood Oct 10 '15 at 22:34