Track / Stage 5 / 70 of 400 #670 of 2000

Problem 670

AIME late

Combinatorics Difficulty 5.2 Find the answer

Task 5. (5 points) On a new website, 2000 users have registered. Each of them invited 1000 (of the registered users) to become friends. Two people become friends only if each of them has invited the other. What is the minimum number of friend pairs on the site?

Your answer

Official solution

Solution. The invitations are a total of 2000. $1000=2000000$ , and the pairs of users on the site are $2000 \cdot 1999 / 2=1999000$ . The number of invitations is 1000 more than the number of pairs, so there are at least 1000 pairs in which invitations have been exchanged and friendships have been formed.

Exactly 1000 friendly pairs are obtained if we arrange all users in a circle and each user invites the next 1000 after themselves (in the clockwise direction). This way, friendly pairs will only form between users who are positioned diametrically opposite.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.