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 triples in all. Let be the number of triples with or edges, and let be the number of triples with or edges. So .
Each point is joined to others, so it is in triples where it is joined to both the other points, and it is in triples where it is not joined to either of the other points. So the total number of triples , where is joined to and or not joined to or is .
This counts the triples times each, and the triples once each, so . Hence .
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.