Answer to Question #466 in Statistics and Probability for daniel

Question

45 people came to the meeting. It turned out that any two of them having the same number of friends among the visitors are not familiar with each other. What is the greatest number of pairs of friends could be among the participants of the meeting?

Answer 1

Here is an example. Since 45 = 1 + 2 + 3 + … + 9, it is possible to divide 45 people into groups of 1, 2, …, 9 people in each. Let the people of a group be not familiar with the members of their group, but all the people from different groups are friends. Then every person from the group k has 45 − k friends. In this case the task is satisfied, and the total amount of pairs of friends is:

((45*44)/2) - (((2*1)/2)+((3*2)/2)+...+((9*8)/2)) = 870

Now we have to prove that there cannot be any bigger amount of pairs of friends. Fix some k, 0 ≤ k ≤ 44. Let there be a person with exactly k friends. According to the task, any of his friends cannot have exactly k friends. Thus, the number of people with exactly k friends is not bigger than 45 − k.

Denote A0, A1, … ,A44 as the amounts of people with respectively 0, 1, …, 44 friends. As shown before, Ak ≤ 45 − k, and besides A0 + A1 + ⋯ + A44 = 45.

We can estimate the total number of pairs:
S = (1/2)*(0*A0+1*A1+...+44*A44) = (1/2)(A44+(A44+A43)+...+(A44+A43+...+A36)+...+(A44+A43+...+A0)) ≤ (1/2)*(1+(1+2)+...+(1+2+...+9)+45+45+...+45) = (1/2)*(45*44−((9+8+...+2)+(9+8+...+3)+...+9)) = 870

Answer. 870