Competition problem — Combinatorics

Library / /38 of 82

Combinatorics Difficulty 5.0 AIME, harder Find the answer United States

Problem:

Paul Erdős was one of the most prolific mathematicians of all time and was renowned for his many collaborations. The Erdős number of a mathematician is defined as follows. Erdős has an Erdős number of $0$ , a mathematician who has coauthored a paper with Erdős has an Erdős number of $1$ , a mathematician who has not coauthored a paper with Erdős, but has coauthored a paper with a mathematician with Erdős number $1$ has an Erdős number of $2$ , etc. If no such chain exists between Erdős and another mathematician, that mathematician has an Erdős number of infinity. Of the mathematicians with a finite Erdős number (including those who are no longer alive), what is their average Erdős number according to the Erdős Number Project? If the correct answer is $X$ and you write down $A$ , your team will receive $\max (25-\lfloor 100|X-A|\rfloor, 0)$ points where $\lfloor x\rfloor$ is the largest integer less than or equal to $x$ .

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Answer: $4.65$ We'll suppose that each mathematician collaborates with approximately $20$ people (except for Erdős himself, of course). Furthermore, if a mathematician has Erdős number $k$ , then we'd expect him to be the cause of approximately $\frac{1}{2^{k}}$ of his collaborators' Erdős numbers. This is because as we get to higher Erdős numbers, it is more likely that a collaborator has a lower Erdős number already. Therefore, we'd expect about $10$ times as many people to have an Erdős number of $2$ than with an Erdős number of $1$ , then a ratio of $5, 2.5, 1.25$ , and so on. This tells us that more mathematicians have an Erdős number of $5$ than any other number, then $4$ , then $6$ , and so on. If we use this approximation, we have a ratio of mathematicians with Erdős number $1, 2$ , and so on of about $1: 10: 50: 125: 156: 97: 30: 4: 0.3$ , which gives an average Erdős number of $4.8$ . This is close to the actual value of $4.65$ .

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.