If X knows Y, then Y knows X.
Probability
Level
3
There are 100 people in a group. We know that, among any four people, at least one knows all the other three. What is the minimum number of people who know everyone else in the group of 100 people?
The answer is 97.
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
The problem is more easily solved by flipping it around and asking "what is the maximum number of people who don't know everybody else in the group of 100 people?" It's clear that if three or less people don't know everybody else, we're fine, since any group of four must contain somebody who knows everybody.
But what about four people, or more? Well, suppose there are four people who don't know everybody else. Then we must be able to find people A,B who don't know each other. If we can find new people C and D who don't know each other, we are done, since in the group A,B,C,D none of the four know all the other three. Otherwise, we must be able to find new people C and D who don't know one or both of A and B, and then clearly in A,B,C,D nobody knows both of A and B, so nobody knows the other three.
Hence we cannot have four people who don't know everybody else, we can have at most three. In the terms of the question, we must have at least 97 people who know everyone else in the group.