2
$\begingroup$

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?

  • 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.2012-04-09

1 Answers 1

3

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.

  • 0
    @user28699: You’re right about (1) and (2). I’ve added a $l$itt$l$e more he$l$p with (3).2012-04-10