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.

Question:

A dealership has $n$ cars. An employee with a sense of humor takes all $n$ keys, puts one of them in each car at random, then locks the doors of all cars. When the owner of the dealership discovers the problem, he calls a locksmith. He tells him to break into a car, then use the key found in that car to open another, and so on. If and when the keys already recovered by this procedure cannot open any new cars, the locksmith is to break into another car. This algorithm goes on until all cars are open.

(a) What is the probability that the locksmith will only have to break into one car?

(b) What is the probability that the locksmith will have to break into two cars only?

share|improve this question
1  
Welcome to math.SE: since you are fairly new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are so far; this will prevent people from telling you things you already know, and help them write their answers at an appropriate level. If this is homework, please add the [homework] tag; people will still help, so don't worry. –  Arturo Magidin Apr 9 '12 at 20:28
1  
Since you're new here, welcome. Here at Math.SE, you should post what you know and what you have tried for the question. Most people do not answer posts with just a question/verbs telling them to answer. Plus, this allows others not to post something you already know. So . . . what have you tried so far? Edit: Arturo beat me by about 5 seconds - only because he pastes his usual message! –  Joe Apr 9 '12 at 20:28
1  
@ArturoMagidin I have a question and will ask it right away: Is the message you post copyrighted? I mean, I am interested to keep a .txt file or on my profile, and use the same message with slight modifications. (I see this one is jumbled a bit--but, I liked some of the previous ones. I'll choose one I find best and let you know if you'll let me use the message here.) Regards, –  user21436 Apr 9 '12 at 20:39
    
@KannappanSampath: If you are talking about the "Welcome" comment above, I cribbed it from someone else, so if it is "copyrighted", then I'm in trouble. Feel free to use it and modify it as you feel is appropriate. –  Arturo Magidin Apr 9 '12 at 21:44
    
@Arturo Yes, I was talking about that. I'll soon start using that. Thank you. –  user21436 Apr 10 '12 at 10:57

1 Answer 1

HINTS: Number the cars from $1$ to $n$ arbitrarily. Give each key the same number as the car to which it belongs. The employee’s prank results in a permutation $\pi$ of $\{1,\dots,n\}$ in which Car $k$ contains Key $\pi(k)$. Write $\pi$ as a product of disjoint cycles.

Now say that the locksmith initially breaks into Car $1$; he will then be able to get into every car whose number is in the cycle containing $1$. Thus, he will need to break into only one car if and only if the permutation is a cycle. Similarly, he will need to break into two cars if and only if the permutation is a product of two disjoint cycles.

  1. How many permutations of $\{1,\dots,n\}$ are there?

  2. How many of them are cycles?

  3. How many of them are a product of two disjoint cycles?

Added: Here’s a little more help with the third question. To get a permutation with two cycles, you have to split $\{1,\dots,n\}$ into two non-empty subsets. Then you have to order each of these subsets to make it a cycle. You already know from (2) how many ways there are to order a set as a single cycle. Be a little careful, though: $(135)(24)$ and $(24)(135)$ are the same permutation.

share|improve this answer
    
1. I believe there are n! permutation as total and 2. in the one cycle (n-1)! and 3. in the two disjoint cycle... I really not sure –  user28699 Apr 10 '12 at 17:45
    
@user28699: You’re right about (1) and (2). I’ve added a little more help with (3). –  Brian M. Scott Apr 10 '12 at 21:24

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.