Thursday, August 16, 2012

The "Mailbox" problem

We have n mailboxes, which each have a key and all keys are distinct. There is a master key which works for every mailbox.

Now, each key is put in one mailbox, and all mailboxes are locked using the master key.

So, what we have here is n locked mailboxes, which each has a key to one of those n mailboxes.

You want to open all the boxes. To start with, you have to break one box, take key from that, and open its corresponding box. When you find key to first box, you have to break another box and so on.

So, given you can break k boxes, what is the probability that you will be able to open all the mailboxes?

Courtesy: Prof. Sharad S. Sane, IIT Bombay.


Sravan said...

Is it that we are breaking open k random boxes in the beginning itself? And then we are asked to calculate the probability of being able to open all boxes?

If so, the solution could be this.

Let, w.l.o.g., 1,2,...k be the numbers of the keys in the k random boxes.

Let P(n,k) be the number of permutations of n elements such that each of the cycle has at least one of the elements from 1,2,3,...k.

Now, consider P(n+1,k). The n+1th element cannot be in a cycle of its own. So, it must be in one of the earlier n cycles.
So, P(n+1,k)= n*P(n,k)

Also, P(k,k)=k!

So, P(n,k)=k*(n-1)!

Probability = P(n,k)/n!=k/n

But if the question doesn't mean that we break k random boxes first, then it'll be different. Then the question will simply be, what is the probability that there are a maximum of k cycles. I don't think this result has been established in combinatorics.

pathankhan salman said...

Your assumption is right, and so is the solution.