Skip to main content
OlympiadHQ

Browse · MathNet

Print

III OBM

Brazil counting and probability

Problem

A graph has 100 points. Given any four points, there is one joined to the other three. Show that one point must be joined to all 99 other points. What is the smallest number possible of such points (that are joined to all the others)?
Solution
Suppose that no point is joined to all the others. Then given any point we can find not joined to . So take arbitrary and . Then take not joined to and not joined to . Then the four points do not meet the required condition. Contradiction.

So find joined to all the other 99 points. Now repeat the argument for the other 99 points, that gives a point joined to the other 98. But it is also joined to , so it is joined to all other 99 points. Now repeat for the other 98 points and so on. The last time we can repeat is when we have already found leaving four points. We can now take joined to the other three and hence to all other 99. Thus we can get at least 97 points each joined to all points except itself.
Final answer
97

Techniques

Graph TheoryInduction / smoothingColoring schemes, extremal arguments