- #76

- 63

- 13

##8##. In a conference there are ##n## persons. Show that there are two persons such that, from the rest ##n - 2## persons, there are at least ##\lfloor \frac{n}{2} \rfloor - 1## persons each of which knows both the aforementioned two persons or else knows no one from them. Suppose that "know someone" is a symmetric relation.

Originally, I interpreted the question as follows

there are at least ##\lfloor \frac{n}{2} \rfloor - 1## persons {

*each of which knows both the aforementioned two persons*}**or else**{*each of which knows no one from them*}but I couldn't solve it.

However, if I interpret it as follows:

there are at least ##\lfloor \frac{n}{2} \rfloor - 1## persons

*each of which {knows both the aforementioned two persons***or else***knows no one from them*}then I think I can solve the problem.

------------------------------------------------------------------------------------------------------------------------------------------------

It is a graph with ##n## vertices, in which if two people know each other, the two vertices are bound by a blue edge, if they do not know each other, then yellow edge. At the vertex ##A##, the number of blue edges is ##b_A##, the number of yellow edges is ##y_A##, while in the ##B## the number of blue edges is ##b_B##, the number of yellow edges is ##y_B##.

##\left[ \frac n 2 \right] - 1 \lt \frac {n-1} 2## inequality is true for all positive n.

Suppose that for each vertex ##A## and ##B## of the graph, there are fewer single-colored edge pairs than ##\left[ \frac n 2 \right] - 1 ##, so it is false what the theorem says. In this case, for each pair of vertices ##A## and ##B##,

*the number of edge pairs of different colors is greater than*##\frac {n-1} 2##. Take one of these ##A## and ##B## pair of vertices.

The following two cases are possible:

(1) ##b_A > \frac {n-1} 2 ## and ## y_B > \frac {n-1} 2##

(2) ##y_A > \frac {n-1} 2 ## and ## b_B > \frac {n-1} 2##

(2) ##y_A > \frac {n-1} 2 ## and ## b_B > \frac {n-1} 2##

However, the above is true for vertices ##A## and ##C##, so

(1) if ##b_A > \frac {n-1} 2 ## then ## y_C > \frac {n-1} 2##,

(2) but if ##y_A > \frac {n-1} 2 ## then ## b_C > \frac {n-1} 2##.

(2) but if ##y_A > \frac {n-1} 2 ## then ## b_C > \frac {n-1} 2##.

However, with respect to the vertex ##B## and ##C## of the graph, we get a contradiction because in both the previous two cases

(1) if ##b_A > \frac {n-1} 2 ## then ## y_C > \frac {n-1} 2## and ## y_B > \frac {n-1} 2##,

(2) but if ##y_A > \frac {n-1} 2 ## then ## b_C > \frac {n-1} 2## and ## b_B > \frac {n-1} 2##.

(2) but if ##y_A > \frac {n-1} 2 ## then ## b_C > \frac {n-1} 2## and ## b_B > \frac {n-1} 2##.

**ps**

I see that I have to write ##\frac {n-2} 2## instead of ##\frac {n-1} 2## above.

Last edited: