1
$\begingroup$

Q.) A party is attended by twenty people. In any subset of four people, there is at least one person who knows the other three (we assume that if A knows B, then B knows A). Suppose there are three people in the party who do not know each other. How many people in the party know everybody else?

It's not possible that there are 4 people who don't know each other is it, but how do we deduce from the given data the no. of people who know everybody else, I can't find any connection between them. In a subset of 4 people, one knows 3 and 3 know that one but it doesn't imply the 3 know each other, I'm out of thoughts at this point...

$\endgroup$
3
$\begingroup$

I am reprensting people by numbers.1,2,3 are the people who don't know each other.

if you select {1,2,3,X} as 1,2,3 does not know each other therefore X knows all of them(X can be any of other 17 persons that is 4,5,6....20.) Now we know every person (other than 1,2,3 ) knows 1,2,3 .

if you select {1,2,X,Y} as we know that X knows 1,2 and Y knows 1,2 (proved above ). but 1 does not know 2. Now there's atleast one person who knows every body and that cannot be 1or 2 (they dont know each other)

So either X knows Y or Y knows X(as knowing each other is mutual). But that mean Y knows X and X knows Y. So we have not put any boundation on X and Y . For example you can pick any 2. Say X=4 and Y can be changed . X=4 knows Y=5,6,7....20. We have already proved X=4 knows 1,2,3. So X=4 knows everybody.

Same arguments could be given when X=5,6,7.....20. Hence all other people expect 1,2,3 know each other. So answer is 17.

$\endgroup$
3
  • $\begingroup$ I understood and the answer is correct but how did you deduce this, please break down your thinking process step by step so I can understand more intuitively and deeply $\endgroup$ Feb 7 '20 at 15:01
  • $\begingroup$ so i have edited my answer , i hope you like it. $\endgroup$ Feb 7 '20 at 15:14
  • $\begingroup$ Ah, nice , I can feel it now, thanks $\endgroup$ Feb 7 '20 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.