2

At a tennis tournament, every group of $s$ participants shares exactly one common friend. Suppose player $Q$ has the largest number of friends. Determine how many friends $Q$ has. You must prove your answer. $s\in\Bbb N$ is a fixed but arbitrary number such that $s\ge 3$.

  • if $A$ is a friend of $B$, then $B$ is a friend of $A$
  • $A$ is not his own friend
  • a group of players is said to have a common friend $x$ iff each player in the group is friends with $x$

I feel this is similar to one of the classic discrete math problems but I am not sure which one. Any leads on how to start this?

Brian M. Scott
  • 616,228
  • 1
    From the statement, it seems that the answer is supposed to be independent of the number of tournament participants. I observe that when there are exactly $s+1$ participants, then player $Q$ (indeed, all players) have exactly $s$ friends. Can this be the answer in general? – Greg Martin Oct 09 '15 at 18:52
  • I expect (but haven't proven) that if there are $s+2$ or more participants, then such a situation is impossible, and that the only scenario is for the graph to be a $K_{s+1}$. Perhaps try proving by contradiction that with more than $s+1$ participants, there must be a subgroup of them of size $s$ with at least two common friends. – JMoravitz Oct 09 '15 at 19:39
  • On the other hand, if there are less that $s$ participants in the tournament, then the condition is vacuously met, and the answer can be anything up to $s-2$. – hmakholm left over Monica Oct 10 '15 at 18:05
  • 3
    The bowtie graph illustrates why we need the condition $s\ge 3$. In fact, for $s=2$ we can make $\deg Q$ arbitrarily large by starting with any number of triangles and identifying one vertex of each. – Brian M. Scott Oct 10 '15 at 18:19
  • 1
    Perhaps helpful: Let the players be $T={t_1,\dots,t_n}$. Define $f$ on the nonempty subsets of $T$ with $\le s$ elements as the “first common friend” $f(A)=\min{i:t_i\mbox{ is a common friend for }A}$. ($f$ is well-defined.)

    For $a\in T$ define $K_a$: Set $a_1=a$; for $1<i\le s+1$, let $a_i=f({a_j}{j<i})$; let $K_a={a_1,\dots,a{s+1}}$. $a_i$ and $a_j$ are friends if $j<i$, so $K_a={a_1,\dots,a_{s+1}}$ is a set of $s+1$ mutual friends. I think (for $s\ge3$) for $a, b \in T$, $K_a=K_b$, so $n=s+1$ and everyone is mutual friends. Considering how $K_a,K_b$ can overlap might help.

     – Steve Kass Oct 11 '15 at 03:31

0 Answers0