Answer to Question #139219 in Discrete Mathematics for nanditha

Question

Suppose that in the world every pair of people either
(a) likes one another,
(b) dislikes one another, or
(c) is indifferent toward one another.
Prove that in any gathering of 17 people, there is a group of three people all of whom satisfy one of conditions (a), (b) or (c).

Answer 1

Among 17 people first we fix one person. Lets denote him by x.

We consider like=Red, Dislike=Blue, Indifferent=Green to simply the writing.

We have to show x is connected to 2 of the remaining people (say $y_{1}$ $,y_2$) among 16 by the same colour (say Red). Now if y1,y2 are also connected by red, then we are done.

By pigeonhole principle there exist 3 group of people A,B,C such that x is connected to every people of A,B,C by Red, Blue, Green respectively and there exist one group containing atleast 6 people (say group A).

Now if there are two people (y1,y2) of A who are connected by Red , then we are done and the required set is $\{y1,y2,x\}$ . If not then any two of them are either connected by Blue or Green.

Now fix one person from A (say y).

Hence again applying pigeon hole principle on the set A$\setminus \{y\}$ there must exist one subset of A (say A1) containing atleast 3 people connected with y by same colour (say Blue).

(Note this colour must be Blue or Green)

Now it is easy to see that if there exist 2 vertices (z1,z2) of A1 which are connected by Blue, in that case $\{y,$ z1,z2$\}$ is the required set

otherwise there exists 3 vertices (z1,z2,z3) of A1 which are connected by Green with each other, in that case $\{z1,z2,z3\}$ will be the required set.