A.Y. Evnin

2000 people registered on a new website. Each of them invited 1000 people to be their friends. Two people are considered friends if and only if each of them invited the other to be a friend. What is the minimum number of pairs of friends that could have formed?
Evaluation. A total of 2,000,000 invitations were sent, while the number of pairs on the site is $1000 \cdot 1999 = 1999000$. There are 1000 more invitations than pairs, so within at least 1000 pairs, two invitations were sent. Therefore, at least 1000 pairs were formed.

Example: Place everyone at the vertices of a regular 2000-gon, and let each person invite the next 1000 people in a clockwise direction. Then, friends will be only those located at opposite vertices.

## Answer

1000 pairs.

## [ Combinatorics (miscellaneous). ] Problem 116247 Topics: [ Extreme Principle (miscellaneous). ] [ Continuity considerations ] Difficulty: $4-$ Classes: 10,11 Authors: Netai I.V., Baranov D.V. In a country with two capitals and several cities, some of which are connected by roads. Among the roads, some are toll roads. It is known that on any path from the southern capital to the northern capital, there are at least 10 toll roads. Prove that all toll roads can be distributed among 10 companies such that on any path from the southern capital to the northern capital, there are roads from each of the companies.

## Solution

Mark the first toll road on each path from the southern capital S to the northern capital N with the number 1. We will prove that on each path $p$, there remain at least 9 unmarked toll roads.

Choose on $p$ the toll road $d$ closest to N that is marked. Since it is marked, it was the first toll road on some path $q$. Travel from S to $d$ along (free roads) path $q$, and then through $d$ along $p$ to N. By the condition, there are at least 10 toll roads on such a path, and only road $d$ is marked. Therefore, there are at least 9 unmarked toll roads on the segment of the path from $d$ to N.

Temporarily declare the marked roads free and mark the first toll road on each path with the number 2. Now, on each path, there remain at least 8 toll roads. Repeating the reasoning, place marks $3, \ldots, 10$ on each path.

Now distribute the roads to the companies according to their "numbers." Distribute the remaining toll roads arbitrarily.

Submit a comment