Problem:
There are 25 people at a party and every pair of them is either friends or strangers. Prove that there are two people at the party who have the same number of friends.
Solution
Solution:
Assume that no two people have the same number of friends. Because the number of friends a person can have ranges from to , we can label the people with their numbers of friends and every label will be used once. Now consider the people labeled and . They cannot be friends, because the person labeled has no friends; but they cannot be strangers, because the person labeled is friends with everybody else. We have a contradiction.
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.