Two person with the same number of friends?

kant
Imagine a population p. What is the probability that two person in p will have the same number of friends?

If you figure out the solution, then explain your reason.

I found this problem in a book. I really like the solution...

outsider
I don't have an answer... but i think you will need to further define what would constitute a friend as many people live on the internet and have internet friends in addition to real life friends.

kant
If marry is a friend to john, then john is a friend to marry. Also, marry cannot be a friend of herself.

gnpatterson
request clarification

are we to assume that friendship is also transitive? i.e. if Albert is a friend of Bob and Bob is a friend of Charlie must this imply that Albert is a friend of Charlie?

kant
gnpatterson said:
are we to assume that friendship is also transitive? i.e. if Albert is a friend of Bob and Bob is a friend of Charlie must this imply that Albert is a friend of Charlie?

no, there is no transitive property involved

Jimmy Snyder
Let P = the cardinality of p. If P is 0, or 1, then the probability is 0. If P is infinite, then there is a possibility that there is, or is not such a pair, but I don't know how to express this as a probability.

For all other values of P and under your assumptions that if a is a friend of b, then b is a friend of a and that a cannot be a friend of a, the answer is

(in white): 1.

The reason is:
The most number of friends anyone can have is P -1, and if someone does, it means that they are friends with everyone. Therefore no one has 0 friends. So we must assign the numbers 1, 2, 3, ... P - 1, to P individuals. By the pidgeon-hole principal, at least two people must be assigned the same number.
If the most number of friends that anyone actually has is less than P - 1, then the pidgeon-hole principal applies as well.

If you do not make these assumptions, then let P = 2, say Adam and Eve. Suppose Adam is a friend of Eve, but Eve is not a friend of Adam, Then there is no pair of individuals with the same number of friends. On the other hand, suppose they were both friends of each other. Then there would be such a pair of individuals. So there is a possibility either way. However, I see no way to express this as a probability.

gnpatterson

I would have to make some assumption about the distribution of friendships being in some way randomn

could i assume that there are p(p-1)/2 friendships that may or may not be made thus 2^(p(p-1)/2) equally possible patterns of the friendships and then apply some of Eulers rules to cancel things down to give me the number of friendships?

this seems somewhat laborious so perhaps if I tackle it the other way

if p=1 then pf=1
if p=2 then pf=1 (either they are friends nf=1 for both or not friends nf=0 for both
if p=3 then pf=? (either no-one friends nf =0,0,0 or 3 ways of doing nf=1,1,0 or 3 ways of doing nf=2,1,1 and case allfriends nf=2,2,2)
pf=1/8 + 1/3*3/8 + 1/3*3/8 + 1/8 = 1/2

if p=4 then pf=? (2^6 poss; either no-one friends nf =0,0,0,0; six ways of 1 friendship nf=1,1,0,0 choosing equals 1/2 the time; 3 ways of pairing friends nf=1,1,1,1; 12 love triangle and gooseberry nf=2,1,1,0 get the equals 1 time in 6; 4 ways to idolise someone nf=3,1,1,1 not getting the god half the time;menage a trois nf=2,2,2,0 4 times getting equal 1/2;nf=2,2,1,1 a broken circle 12 times and equal 1/2; nf=3,2,2,1 can be done 12 ways it is the inverse of the love triangle and the gooseberry,invert the pairs which become circles of admiration; and singles to get nf=3,3,2,2 and finally love all round to get nf=3,3,3,3

pf=1/64 + 1/2*6/64 + 3/64 + 1/6*12/64 + 1/2*4/64 + 1/2*4/64 + 1/2*12/64 + 1/6*12/64 + 3/64 + 1/2*6/64 + 1/64 = 28/64

this now looks like even more work

however having worked through all of this I can now see the easy way to look at the problem and the minor errors in my calculations are pointless as it is so much easier to do. I will have to figure out how to type it in as a non-spoiler as I'm sure others will want to work it out

kant
Let see more solutions from other people

Jimmy Snyder
I need to clarify the situation where the cardinality of p is infinity. I knew that the pidgeon-hole approach would not work here and without further thought I declared that a friendship relationship could be found where there was no pair of individuals with the same number of friends. However, when I tried to actually describe such a relationship, it took some time. It turns out that I was correct after all, but now I know that I am correct.

Let 1 be friends with 2.
Let 2 be friends with 1 and with 3.
Let 3 be friends with 2 and with 4, and 5.
Let 4 be friends with 3 and with 6, 7, and 8.
Let 5 be friends with 3 and with 9, 10, 11, and 12.
Let 6 be friends with 4 and with 13, 14, 15, 16, and 17.

In other words, except for 1, assign every person n exactly one friend whose number is lower than his own, and n - 1 people who have not yet been assigned any friends. Then there will be exactly one person with 1 friend, 1 person with 2 friends, one person with 3 friends, etc. and no two people with the same number of friends.

However, this only takes care of the case where the cardinality of p is a countable infinity. Under the continuum hypothesis, for the first uncountable infinity $\aleph_1$, the probability is 1. The reason for this is that there are only countably many cardinalities less than or equal to $\aleph_1$. Namely, the integers, $\aleph_0$, and $\aleph_1$. And these countably many cardinalities must be assigned to $\aleph_1$ people. Again, by the pidgeon-hole principle, two people must share a cardinality of friends.

I would like to use the same argument to imply that the probablility is 1 for all $\aleph_{n} n = 1, 2, 3, ...$. However, this would require something like the continuum hypothesis for each pair $\aleph_n,\ \aleph_{n+1}$. This goes beyond my knowledge of infinities.

Last edited: