Maths Olympiad Prep

Library / /108 of 196

Combinatorics Difficulty 5.3 AIME, harder Prove it Soviet Union

Problem:
A graph has 30 points and each point has 6 edges. Find the total number of triples such that each pair of points is joined or each pair of points is not joined.

Solution

Solution:
There are 30×29×28/6=406030 \times 29 \times 28 / 6 = 4060 triples in all. Let mm be the number of triples with 00 or 33 edges, and let nn be the number of triples with 11 or 22 edges. So m+n=4060m + n = 4060.

Each point is joined to 66 others, so it is in 6×5/2=156 \times 5 / 2 = 15 triples where it is joined to both the other points, and it is in 23×22/2=25323 \times 22 / 2 = 253 triples where it is not joined to either of the other points. So the total number of triples (a,b,c)(a, b, c), where aa is joined to bb and cc or not joined to bb or cc is 30(15+253)=804030(15 + 253) = 8040.

This counts the mm triples 33 times each, and the nn triples once each, so 3m+n=80403m + n = 8040. Hence m=1990m = 1990.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.