Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a Math question I read and I badly want to know the answer. It says; There are twelve people who own 12 phones.One of them(who owns the most valuable phone) suggested to write down their names and the phone model on billets and toss them.Then to exchange the phones according to the phone model on the billets they received after the tossing. The questions is;what is the probability of not receiving the same billet which is written by himself(or herself)?

And the answer I suggested is 11/12;which is wrong!

Can someone help me with this? Thank you in advance.

share|improve this question
1  
The question is a little foggy, imo: What is the probability of who not receiving his own billet? Does everybody get at the same time a billet or they draw them by turn out of a bowl or something? Is the question perhaps "what's the prob. that exactly, at least one, at most one receives his own...etc.? –  DonAntonio Nov 14 '12 at 15:13
1  
The person with the valuable phone is being generous! The probability that a particular person, say Alicia, does not receive her own phone is indeed $11/12$. But maybe the question is "what is the probability no one gets her own phone." Then the solution is quite a bit harder. It is, however, a standard problem with a very nice answer. –  André Nicolas Nov 14 '12 at 15:14

1 Answer 1

Like you suggested, the probability that a single person does not receive their own phone is $11/12$, so if you know that's incorrect, the question is most likely "What is the probability that no person receives their own phone?"

Consider how many different ways there are to distribute 12 phones to 12 people. For the first person, you have 12 phones you could give him/her, for the second you have 11, since you already gave one away, and for the third you have 10, and so on. If we multiply all the options of different phones that each person could get this way, we get what we wanted to find: $12\cdot 11\cdot \ldots \cdot 2 \cdot 1 = 12! = 479,001,600$ different ways. This is called a permutation; we are permuting the 12 phones throughout 12 people.

Now in this specific problem, we are looking for the number of different ways to distribute $n$ phones to $n$ people such that no single person receives the phone that they started with. Let's say there are $D(n)$ ways to do this and approach it the same way we did above. The first person has $12-1 =11$ phones that they could receive that aren't their own. Let's say they receive the $k^\text{th}$ person's phone. Now, however, the number of phone options for the next person depends on whose phone the $k^\text{th}$ person received. For this, there are two options:

  1. The $k^\text{th}$ person received the first person's phone. In this case, we know they didn't receive their own, so now there are $10$ people without phones and $10$ phones left. To distribute these to make sure no one else gets their own phone, this is the same problem we started with, except with 2 less phones. So now we must solve for $D(10)$.
  2. The $k^\text{th}$ person did not receive the first person's phone. They could still receive their own phone, though, so we want to make sure they don't. Thus we still need to distribute $11$ phones to $11$ people without giving anyone their own phone, so this problem is now $D(11)$.

We can combine these situations into one expression for $D(12)$. We said there are $11$ options for the first person, and after that either there are $D(10)$ or $D(11)$ ways left. this gives a useful recurrence relation:

$$D(12)=11\cdot(D(10)+D(11))$$.

In fact, nothing we have done was specific to these choices of numbers. In general, this is true: $D(n)=(n-1)(D(n-2)+D(n-1))$. Let's use this now to get a general closed form for how to distribute $n$ phones to $n$ people without giving anyone their own phone.

The part that remains is to solve the recurrence relation for a closed form. Luckily, there is a great explanation of how to do this on this blog.

Spoiler: you'll get that $\displaystyle D(n)=n! \sum_{k=0}^n \frac{(-1)^k}{k!}$, so $D(12)=176,214,841$. Dividing this by the total number of permutations gives your probability, which is about $37\%$.

Historical Note: This is a classic problem referred to as finding the number of "Derangements of $n$". It was first proposed in 1708 and solved in 1713 by a French mathematician named R.P. de Montmort.

share|improve this answer
    
Thank you so much for the clear elaboration. –  Grazel Nov 18 '12 at 6:17

Your Answer

 
discard

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.