Group of people
There are 17 people In a group. Each person knows exactly four people from the other 16. (If A knows B, then B knows A.)
True or False?
There will be two people for sure who don't know each other and don't have common acquaintances.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Assume John is a member is this group .
John knows exactly 4 members.(A,B,C,D)
each of of these 4 members , knows 4 other members , then John is one of these 4 , because (if A knows B, then B knows A)
so each one of them knows 3 members plus John ,
let's say , A knows (A1,A2,A3) ... D knows(D1,D2,D3)
Without limitation of generality , if A1=D3,so we got that John's friends knows less than 3*4=12 person, so John have 4 friends and there are less than 12 person who have common acquaintances with John , so we reached at maximum 15 person who knows John or have common acquaintances with him , this means , at least one person don't know John , and don't have common acquaintances with him , so it's over , the answer is "yes".
Without limitation of generality , if A1 don't know any Di, A1 is not the same person Di,so A1 don't know D, and also don't have common acquaintances with D, because D knows just John and D1,D2,D3 , and A1 don't know any of them .so it's over , the answer is "yes".
*According to this , from now we can assume that Without limitation of generality , any Ai knows exactly one Bi and one Ci and one Di ,because he knows A and one of each group , and the sum of the people he knows must be 4 ,
A1 don't know A2,A3,as we assumed, Without limitation of generality , he knows B1,C1,D1,so no one of B1,C1,D1 knows A2,A3 because we assumed any one of them knows exactly one person from the group A1,A2,A3 , and he is A1 because he knows them ,
I mean that different members Ai knows different member Bi,Ci,Di ,we assumed this Without limitation of generality , so this is also right to the other groups .
C1 knows {C,B1,A1,D1} and have common acquaintances => C gives {John,C2,C3}, B1 gives B , A1 gives A , D1 gives D , so C1 don't know B2,B3 and don't have common acquaintances with them ,,,, B2 know B and Ci , where i!=1 , so he must know A1 or D1 to have common acquaintances with C1 , the same thing with B3 , he must know A1 or D1 .,But A1 knows B1 so both B2 and B3 must know D1 and not A1 , so we got two members Bi that knows D1 , but we said that Di must know one Bi , so we got that we assumed something wrong , and the answer must be "yes" .