Maths Olympiad Prep

Library / /4 of 6

Combinatorics Difficulty 6.3 National olympiad Prove it Brazil

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 XX we can find YY not joined to XX. So take arbitrary AA and CC. Then take BB not joined to AA and DD not joined to CC. Then the four points A,B,C,DA, B, C, D do not meet the required condition. Contradiction.

So find X1X_1 joined to all the other 99 points. Now repeat the argument for the other 99 points, that gives a point X2X_2 joined to the other 98. But it is also joined to X1X_1, 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 X1,X2,,X96X_1, X_2, \dots, X_{96} leaving four points. We can now take X97X_{97} 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.