Question

4) A class has 8 students. Suppose that three students X, Y and Z do not know each other. X knows 4 students of the class, Y knows 3 students of the class. At least how many students must Z know to make sure that always there is one student that knows X, Y, and Z? (Explain by using a graph to model the relationships).

Answer 1

solution:

As per given information, there are 8 students in the class, There students X, Y, and Z do not now each other. Suppose the remaining students are S1, S2, S3, S4, S5.

We know that X knows 4 students and class and X does not know Y and Z. So these 4 students must be among S1, S2, S3, S4, S5.

For Y, Y knows 3 students and class and Y does not know X and Z. So these 3 students must be among S1, S2, S3, S4, S5.

Because X and Y know students among S1, S2, S3, S4, S5 only, there will be some common friends(knows each other) of X and Y. They can either have 2 common friends or they can have 3 common friends.

Case-1: 2 common friends of X and Y-

Now we represent the relationship of students using a graph. Each node of the graph is a student, and the edge between two students represents that they know each other.

This graph represents the relationship of students except for student Z.

Y Х S4 S3 S1 S2 S5

Now we can see that If Z knows one of S1 or S2 then there will be a person who knows X, Y, and Z. So to always ensure that there is one common friend of X, Y, and Z. Z should at least have 4 friends. If Z has four friends then at least one of then must be among S1, S2.

Case-2: 3 common friends of X and Y-

Relationship graph in this case:

Y х S4 S3 S1 S2 S5

Now we can see that If Z knows one of S1 or S2 or S3 then there will be a person who knows X, Y, and Z. So to always ensure that there is one common friend of X, Y, and Z. Z should at least have 3 friends. If Z has 3 friends then at least one of then must be among S1, S2, S3.

Answer: To always have one common friend of X, Y, and Z. We have to consider set of friends which always have one common friend. So to ensure we take the worst case (maximum) of both the above cases.

So Z should at least have 4 friends so that there is at least one common friend of X, Y, and Z.

than you...

please give me thumb up