Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Two person with the same number of friends?

  1. Aug 12, 2005 #1
    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...
  2. jcsd
  3. Aug 12, 2005 #2
    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.
  4. Aug 12, 2005 #3
    If marry is a friend to john, then john is a friend to marry. Also, marry cannot be a friend of herself.
  5. Aug 12, 2005 #4
    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?
  6. Aug 12, 2005 #5

    no, there is no transitive property involved
  7. Aug 12, 2005 #6
    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.
  8. Aug 12, 2005 #7
    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
  9. Aug 12, 2005 #8
    Let see more solutions from other people :smile:
  10. Aug 12, 2005 #9
    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 [itex]\aleph_1[/itex], the probability is 1. The reason for this is that there are only countably many cardinalities less than or equal to [itex]\aleph_1[/itex]. Namely, the integers, [itex]\aleph_0[/itex], and [itex]\aleph_1[/itex]. And these countably many cardinalities must be assigned to [itex]\aleph_1[/itex] 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 [itex]\aleph_{n} n = 1, 2, 3, ...[/itex]. However, this would require something like the continuum hypothesis for each pair [itex]\aleph_n,\ \aleph_{n+1}[/itex]. This goes beyond my knowledge of infinities.
    Last edited: Aug 12, 2005
  11. Aug 12, 2005 #10


    User Avatar
    Science Advisor
    Homework Helper

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook