Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose there is a city with population $n$. Suppose also that, for each person, there's a chance $p$ that their soulmate is living in the same city.

In this city there's a club with $m$ members. What's the chance that there are no pairs of soulmates in this club?

Here's my answer

Let's analyse a person who belongs to the club. They have a chance $1-p$ of having their soulmate in another city. If their soulmate lives in the city, then there's a chance $\frac{n-m}{n}$ of the soulmate not belonging to the club.

There are $m$ members in the club so the total chance of not having any pairs of soulmates is:

$$\left( 1-p + p\frac{n-m}{n}\right)^m=\left( 1 +p\frac{n-m-n}{n}\right)^m =\left( 1 -p\frac{m}{n}\right)^m$$

Here's my doubt

I assumed all events are independent, but clearly if $m-1$ persons don't have a soulmate in the club, then the last person can't have a soulmate in the club either. If we assume soulmate is a symmetric property, then what's the proper solution?

share|cite|improve this question
Would anyone mind terribly if I change all instances of "he" and "his" to "they" and "their" in this question? – Rahul Nov 18 '12 at 19:55
No, please change. – Ricbit Nov 18 '12 at 19:55
up vote 1 down vote accepted

I think you're right about the independence problem.

Perhaps a better way to look at it would be to consider all $k$ people living in the world both inside and outside your city. Then, by your soulmate property, we can divide these $k$ people into pairs of soulmates.

If $n$ is the population of the city, then the probability of one soulmate living in the city is $n/k$. The probability that one soulmate belongs to the club is $(n/k)(m/n)=m/k$, because $m/n$ is the probability that a given city resident belongs to the club.

Then, the probability that both soulmates belong to the club is $(m/k)^2$, and the probability that the pair together don't belong is $1-(m/k)^2$. The probability that no pair belongs whatsoever is this probability raised to the power of the number of pairs, which is $k/2$; that is, $$ \text{P[no pair belongs]} = \left( 1-\left(\frac{m}{k}\right)^2 \right)^{k/2} $$

We can put this answer in terms of your variables. You say that given one person, the probability that their soulmate lives in the city is $p$. But, if the events "soulmate 1 lives in the city" and "soulmate 2 lives in the city" are independent (that is, soulmates are not predestined to live in the same place), then the probability that anyone lives in the city is $p$. Then we have $$ \text{population of city} = \text{total population} \times \text{probability of living in city} \implies n=kp $$and our answer is $$ \text{P[no pair belongs]} = \left( 1-\left(\frac{pm}{n}\right)^2 \right)^{n/2p} $$ If there are 7 billion people in the world and our club has 1000 members, the outlook is unfortunately bleak:

share|cite|improve this answer
Thanks for the answer! – Ricbit Nov 19 '12 at 0:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.