thanks, aphie, for a challenging puzzle, having me to brush up on my combinatorics, and ruining my weekend... so here we go: as several people above replied, the number of all possible permutations is 30! (ie 1*2*3*4*...*30). let's divide those permutations to 31 groups as follows: 1. permutations that have 0 matches out of 30. let's denote the size of this group by M(30,0). clearly, the M(30,0) is a very large number. 2. permutations that have 1 match: M(30,1) 3. ...so forth 30. permutations that have 29 matches: M(30,29). clearly, M(30,29)=0 since there is no way to distribute 30 letters and end up with only one in the wrong mailbox. however, let's keep that "group" for consistency. 31. permutations that have 30 matches: M(30,30)=1, obviously. now, let's look at group M(30,1) -- ie all permutations that have only one match. let's divide the group to subgroups, depending on which mailbox received the correct letter. clearly, there are exactly 30 such subgroups of equal size. as, by definition, there are no other matches in the remaining 29 mailboxes, the size of each such subgroup is - using our notation - M(29,0). hence, we get M(30,1)=30*M(29,0). doesn't sound very useful, but bear with me. if we look at the remaining groups of 2 and more matches, we see that we can perform a similar sub-grouping, depending which particular 2, 3, etc. mailboxes got lucky. as the number of all possible picks of m elements out of the set of n is well known from the combinatorics to be C(n,m) = n!/(m!*(n-m)!), we get that, generally, M(30,m) = C(30,m)*M(30-m,0) or, in plain english, we get the size of each m-match group by taking all possible combinations of m mailboxes, C(30,m), and taking into account that each such combination will contribute exactly M(30-m,0) permutations, because of the requirement that there are no more matches in the remaining 30-m mailboxes. obviously, even more generally, we can write: M(n,m) = C(n,m)*M(n-m,0) and, as a side note, i must define M(0,0)=1 in order for the above to play out. (i know all the above may have been a bit difficult to follow, but luckily the hardest part is over.) now. obviously, if we sum all the M-groups, we get back the number of all possible permutations: M(30,0)+M(30,1)+M(30,2)+...+M(30,30) = 30! hence: M(30,0) = 30! - M(30,1) - M(30,2) - ... - M(30,30) or, substituting the value for M(n,m) from above: M(30,0) = 30! - C(30,1)*M(29,0) - C(30,2)*M(28,0) - ... - C(30,30)*M(0,0) voilla! we just derived a method to get M(30,0) from M-s of lower order! but we don't know the M(29,0) etc. do we? sure, but nothing (except boredom) stops us from calculating all of them using the following iteration: 1. M(1,0)=0, as with 1 mailbox only we'll never get a "no match" scenario 2. M(2,0)=2! - C(2,1)*M(1,0) - C(2,2)*M(0,0) = 2 - 2*0 - 1*1 = 1 3. ...and so forth until M(29,0) and M(30,0). those two we keep i'll leave the above calculation as an excercise to the reader, as god knows i've already wasted a big chunk of my weekend on this stuff... i did try to simplify the above calculation -- i failed. now, what can we do with these M(29,0) and M(30,0)? well, they are the very keys to the answers, because we can calculate odds of a certain permutation-group by dividing the size of that group by total number of permutations (30!). hence: a) the odds that one (and only one) letter was placed correctly, are M(30,1)/30! = 30*M(29,0)/30! = M(29,0)/29! b) the odds that at least one letter was placed correctly are (as mr. sub. correctly pointed out) 1 - M(30,0)/30! c) the odds that NO letters were placed correctly, are, obviously, M(30,0)/30! d) if you really can't answer this by yourself by now, why the heck did you bother to read so far? - jaan
Well, I could see that but was not smart enough to re-invent Inclusion-Exclusion Principle. However, after I learned about that principle, the problem became fairly simple. First, we'll get (basic combinatorics from High School curriculum has been omitted for the sake of the beauty of the final formula) that answer to (b) is 1 - 1/2! + 1/3! - 1/4! + 1/5! - ... + 1/29! - 1/30! from there we proceed to (c), which is obviously 1-(b) 1/2! - 1/3! + 1/4! - 1/5! + ... - 1/29! + 1/30! and (a), which is (c) for 29 mailboxes 1/2! - 1/3! + 1/4! - 1/5! + ... - 1/29!
Jaan and igsi -- great answers! You guys are really smart! Now ask this problem to the guy at the copy machine at work and let him go back to his desk until he either solves it or gets fired trying.
This approaches 1/e (0.367879...) as the number of letters gets larger. 1/e = 1/2! - 1/3! + 1/4! - 1/5! + ................................... to infinity Since the letters are placed in the mailboxes at random, the probability that any single one is correctly matched is 1/n, where n is the number of letters. In order to find the average number of matches, let Xi be a Bernoulli random variable which is either 1, if the i'th letter was correctly matched, or 0 otherwise. Then the total number of correct matches is X = X1 + X2 + . . . + Xn. The expected value of any Xi is E[Xi] = P(Xi = 1) = 1/n , so the average number of matches is E[X] = E[X1 + X2 + ... + Xn] = E[X1] + E[X2] + .... + E[Xn] = 1/n + 1/n + .... + 1/n = 1 Thus, regardless of how many letters we try to match at random, the average number of matches will be 1.