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]

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]

thanks for quick reply

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.

 

[NateTG]

Each of the p people is friends with from 0 to p-1 people.
Now, let's assume, by contradiction, that there is some possibility that everyone has a different number of friends. Since there are only p possible choices, it must be the case that there is a representative for each number of friends in the population. Specifically, there must be a person with p-1 friends. Clearly, this person must be friends with every other person in the population. There must also be a person with 0 friends, who cannot be friends with anyone else in the popuation. If the two are different people, then this is a contradiction.

This covers all but the trivial cases: if p=0 or p=1 the probability is 0; otherwise the probability is 1.