Problem of the Day: June 19

Alphonse and Beryl play a game involving $n$ safes. Each safe can be opened by a unique key and each key opens a unique safe. Beryl randomly shuffles the $n$ keys, and after placing one key inside each safe, she locks all of the safes with her master key. Alphonse then selects $m$ of the safes (where $m < n$), and Beryl uses her master key to open just the safes that Alphonse selected. Alphonse collects all of the keys inside these $m$ safes and tries to use these keys to open up the other $n - m$ safes. If he can open a safe with one of the $m$ keys, he can then use the key in that safe to try to open any of the remaining safes, repeating the process until Alphonse successfully opens all of the safes, or cannot open any more. Let $P_m(n)$ be the probability that Alphonse can eventually open all $n$ safes starting from his initial selection of $m$ keys. Find (with proof) a general formula for $P_m(n)$.

Edited to add solution: We prove by induction that Pm(n) = m/n.

Note first that the initial distribution of the keys in the n safes amounts to some permutation of {1,...,n}. Call that initial permutation p.

Step 1: Suppose m=1, so Alphonse gets only one safe initially opened.  Alphonse can then open all of the safes if and only if p is a single cycle. There are n! possible permutations of the n keys, and (n-1)! permutations forming a single cycle, so the probability that Alphone can open all the safes is (n-1)!/n! = 1/n.

Step 2: We can now get a recursive relation between the n+1-safe-case and the n-safe-case. Suppose that we have n safes and m initially opened safes. Look inside one of the opened safes and remove the contained key. There are now two cases:

Case 1: The contained key is for one of the initially opened safes. In that case the key is useless. That safe can now be ignored, and we're left with n safes, m-1 of which have been opened. That's thus P(m-1)(n).

Case 2: The contained key is for a safe not initially opened. In that case, we can ignore that safe, open the safe that the key matches, and we're left with n safes, m of which have been opened. That's thus Pm(n).

Case 1 has a probability of m/(n+1), and Case 2 has a probability of (n+1-m)/(n+1). So we get the recursive relation:

Pm(n+1) = m/(n+1) * P(m-1)(n) + (n+1-m)/(n+1) * Pm(n).

Step 3: We now prove by induction on double induction on m and n that Pm(n) = m/n.

Note that Step 1 already gives us the base case m=1 and n arbitrary. So now fix some m and n and suppose Pk(j) = k/j for all k<=m and all j < n. Then by our recursive relation we have:

Pm(n) = m/n * P(m-1)(n-1) + (n-m)/n * Pm(n-1)

By the inductive hypothesis, that gives us:

Pm(n) = m/n * (m-1)/(n-1)  + (n-m)/n * m/(n-1)

With a bit of algebra, we get Pm(n) = m/n.

(Problem source: 2014 Canadian Mathematical Olympiad Qualification #2)

Comments

Post a Comment

Popular posts from this blog

Problem of the Day: June 21

A magical castle has n identical rooms, each of which contains m distinguishable doors arranged in a line. In each room i<n, there is one door that takes you to room i+1, and all other doors take you back to room 1. In room n, there is one door that takes you out of the castle, and all other doors take you back to room 1. When you go through a door into a room, you are unable to tell which room of the castle is is (and there is no way of marking rooms). You also cannot tell which doors have been opened before. Determine for which pairs (n,m) there is a strategy that guarantees escape from the castle, and explain the strategy. Edited to add solution: Here's a starting thought: if we could reliably know when we are in room 1, we could solve the problem easily for any n and m. We would then: 1. Enumerate all length n sequences from the alphabet {1,...,m}. 2. For each sequence in that list, (i) get to room 1, and (ii) then follow that sequence. Eventually we'd get to the c...
Read more

Problem of the Day: June 12

Find all positive integers x, y, and z satisfying x 2 + y 2 + z 2 = 2xyz. (As usual, give solutions in comments to this post. On Friday I'll post some combination of my own solution and the most elegant approaches suggested by others.) Edited to add solution : If x 2 + y 2 + z 2 = 2xyz, then x 2 + y 2 + z 2 must be even. Thus there are two cases to consider: 1. One of x, y, z is even and two are odd. 2. All three of x, y, and z are even. Start with case 1. Assume (without loss of generality) that x is even, so x = 2a. Then we have 4a 2 + y 2 + z 2 = 4ayz. But then y 2 + z 2 must be a multiple of 4. But odd numbers are always 1 mod 4, so this is impossible. Thus case 1 can't be achieved. Now consider case 2. We have x=2a, y=2b, and z=2c. Thus 4a 2 + 4b 2 + 4c 2 = 16abc, or a 2 + b 2 + c 2 = 4abc. So let's now focus on this new equation. Again we  need the sum to be even, so we need either one or three even numbers. But one even and two odd...
Read more