Assume integer $m \geq 2.$ There are $3m$ people in a meeting, any two of them either shake hands with each other once or not.We call the meeting "$n$-interesting", only if there exists $n(n\leq 3m-1)$ people of them, the time everyone of whom shakes hands with other $3m-1$ people is exactly $1,2,\cdots,n,$ respectively. If in any "$n$-interesting" meeting, there exists $3$ people of them who shake hands with each other, find the minimum value of $n.$
Problem
Source: 2018 China Southeast MO Grade 11 P6
Tags: combinatorics
31.07.2018 11:21
2m+1 is the answer
31.07.2018 14:31
We claim that the answer is $2m+1$. We can consider people and hand-shaking as vertices and edges of a graph $G$.First suppose that the meeting is $2m+1$-interesting,and there are no triangles.Let $v_1,v_2,\cdots,v_{3m}$ be vertices of $G$ and $V_{3m}$ is adjacent with $V_i,1 \leq i \leq 2m+1$,then these $2m+1$ points are not anjacent with each other,so they have degree at most $m$.So the $m$ vertices who have degree $m+1,m+2,\cdots,2m$ must be among $v_{2m+2},\cdots,v_{3m-1}$,but there are only $m-2$ vertices,contradiction. Now is the construction part.Let $u_i(1 \leq i \leq m),v_j(1 \leq j \leq 2m)$ be vertices of $G$,$u_i$ and $v_j$ are adjacent if and only if $j>m$ or $j<i$,then it's $2m$-interesting but a bipartite graph. So we conclude that $n_{\min} = 2m+1$.
01.08.2018 22:23
J_bucca wrote: First suppose that there are no triangles in $G$,then $G$ is a bipartite graph. It's wrong.
01.08.2018 23:45
Ummm, the answer is $2m+1$ First, we construct $2m$ we partition $3m$ people in to groups $A,B,C$ with $m$ people in each group now, let person number $i$ , $1\leq i \leq m$ of group $B$ connect with people number $1,2,...,i$ of group $A$ and connect to all people in group $C$ we see that people in group $A$ will have deg $1,...,m$ and $B$ will have deg $m+1,..., 2m$ Hence, $2m$ people in group $A,B$ is $2n$-interesting and of course, there's no triangle Now, suppose we have $2m+1$-interesting, consider the person with degree $2m+1$ called $X$ since there are at least $m$ more person with degree $>m $,there must exists a person $Y$ with degree $> m$ that connects with $X$. (There are $m-1$ person who doesn't know $X$) Since $Y$ has degree $>m$ , he must knows another person $Z$ in the group of $2m+1$ people who $X$ knows. hence $X,Y,Z$ knows each other as desired
02.08.2018 07:51
Yes.I was wrong