Thread: Matching problem View Single Post
 2021-06-02, 12:44 #1 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 22·33·5·11 Posts Matching problem Suppose you have n letters and n addressed envelopes that you need to match. You can find matches by pairing all letters with envelopes and a friend will tell you how many matches there are(not which). What is the expected number of times you need to pair the letters with envelopes to get all matching? What is the maximum number of pairings you could need to find all matches? What would your strategy be to minimize the above numbers? Do they have the same solutions? For easier discussion let's use n=10 as an example although a general formula would be great.