Well, suppose they don’t. If there are n Welshmen in the world, each can have any number of Welsh friends from 0 to n-1 (he can’t be friends with himself). If we are to arrange things so that no two Welshmen have the same number of friends, then the first must have 0 friends, the next 1 friend, and so on. But then the loneliest Welshman has no friends and the most popular is friends with every Welshman but himself. This is a contradiction. Hence there must be some overlap — at least two Welshmen must have the same number of friends.

This is essentially the same idea as in Hand Count. I think it appeared originally in the Litton Problematical Recreations series.