Solution to Suppose that in the world every pair of people either (a) likes one another, (b) … - Sikademy
Author Image

Archangel Macsika

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).

The Answer to the Question
is below this banner.

Can't find a solution anywhere?


Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

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.

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3645-qpid-2344