Solution to Puzzle #146: The Proud Party Goers

Apologies for not being able to post last weekend, ended up in parenting duties more than I bargained for!

This was not a very difficult puzzle, but I did not get as many solutions. Congratulations to Suman Saraf, Gautam Kumar and Abhinav Jain for posting this puzzle.

The answer is is N-2/N, here is the explanation.

The largest share of “proud” people at the party — those who have more friends than their friends, on average — is (N-2)/N. To see why, let N>3 be the number of people at the party, and call two particular people in attendance X and Y. Suppose everyone is friends with everyone else, except that X and Y are not friends with each other. (In math terms, you have a complete graph with one edge removed.) In this case, it’s easy to see that everyone is proud except X and Y. So the largest share of proud people is (N-2)/N, which converges to 1 as the party gets bigger, that is, as N goes to infinity.

Hope you all enjoyed the puzzle.

This entry was posted in Solution and tagged , , . Bookmark the permalink.