Suppose there are 100 people. Some know each other and some do not.
Let us call a pair of people close if there exists a group of at least 50 people (excluding the pair itself) such that everyone in this group knows either both people in the pair or none of them.
Prove that a close pair exists.
Edits
- Knowledge of self does not count
- All connections are mutual (Alice knows Bob means Bob knows Alice)
- The group of 50 does not include the pair itself
This is only a partial answer, as it proves a weaker statement with $50$ replaced by $49.$ First let me restate the problem in a less confusing, more straightforward form:
I don't know how to prove that, but a simple counting argument proves the following:
Proposition. If each edge of the complete graph $K_{99}$ is colored red or blue, then there are two vertices which are connected by at least $49$ monochromatic paths of length $2.$
Proof. Let $V$ be the vertex set of $K_{99}.$ Let $p$ be the number of monochromatic paths of length $2.$ For $v\in V$ let $p_v$ be the number of monochromatic paths of length $2$ with midpoint $v.$ For $u,v\in V,u\ne v,$ let $m_{u,v}$ be the number of monochromatic paths of length $2$ from $u$ to $v.$ Let $m=\max\{m_{u,v}:u,v\in V,u\ne v\}.$
On the one hand, clearly, we have $$p\le\binom{99}2m.\tag1$$ Now the minimum possible value of $p_v$ is $2\binom{49}2,$ attained only if $v$ is incident with $49$ red edges and $49$ blue edges. Moreover, it is not possible for this minimum to be attained by all $v$ simultaneously, as the subgraph consisting of the red edges would then be a $49$-regular graph on $99$ vertices. Thus we have $$p=\sum_{v\in V}p_v\gt99\cdot2\binom{49}2.\tag2$$ Combining $(1)$ and $(2)$ we get $$m\gt\frac{99\cdot2\binom{49}2}{\binom{99}2}=48,$$ whence $m\ge49.$
Remark. The same argument shows that, if each edge of the complete graph $K_{4t-1}$ is colored red or blue, then there are two vertices which are connected by at least $2t-1$ monochromatic paths.