HMMT-Nov 2010 guts, Problem 36

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$.

Solution: 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 . $\fbox{4.65}$.

Answer: 4.65