On sport games there was 1991 participant from which every participant knows at least n other participants(friendship is mutual). Determine the lowest possible n for which we can be sure that there are 6 participants between which any two participants know each other.
Problem
Source: Middle Europe Mathematical Olympiad 2009 TST First Day Second problem
Tags: induction, graph theory, combinatorics unsolved, combinatorics
13.09.2009 18:48
Matematika wrote: On sport games there was 1991 participant from which every participant knows at least n other participants(friendship is mutual). Determine the lowest possible n for which we can be sure that there are 6 participants between which any two participants know each other. Remember that we had an old result that :given a graph having kn+1 vetices,and if the degree of each vertex is larger than and equal to (k-1)n+1 ,we will find a complete graph K_{k+1}.you can prove that result by induction following n. To given a graph with each vertex'degree >=(k-1)n and it does'nt contain any complete graph ,we can order all vertices by 1,2,...kn+1 respectively,and connect two vertices i,j of its if (i not $ \equiv$ j mod k) So my answer is 1593. Correct my solution if there is any mistake.
16.09.2009 01:53
We can also solve it using Turan's theorem. By using it we get that among simple Graphs with $ 1991$ vertices and without any $ K_6$, $ T_{1991,5}$ has the maximum edges and it is constructed as follows:$ 1$ part with $ 399$ vertices,$ 4$ parts with $ 398$ vertices and all the parts are empty-edges and each vertice is connected to all the vertices of all other parts.by analysing this graph we can understand easily that each vertice's degree is at least $ 1592$.so we can conclude that if $ n \geq 1592$ then we can construct a graph that doesn't have any $ K_6$.But if $ n \geq 1953$ then $ e(G) \geq e(T_{1991,5})$ so we can conclude that $ G$ must contains $ K_6$.so $ n = 1593$.
06.05.2022 08:20
We claim the answer is $n=1593$. We translate to graph theory. First, using turan's graph $T_{1991,5}$ we construct a $5-$partite graph where everyone knows at least $1592$ people. This establishes $n\ge1593$. Hence, if $E$ is the number of edges in the graph, we know $2E=\sum\deg v\ge1593\cdot1991>1592\cdot1992$. Then, since $T_{1991,5}$ has $\frac12\cdot(4\cdot398\cdot1593+399\cdot1592)=\frac12\cdot1593\cdot1991$ edges, by Turan's theorem it follows there must be a $K_6$ subgraph when $n=1593$. $\blacksquare$