View Single Post
Old 2021-06-02, 12:44   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

3×1,979 Posts
Default 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.
henryzz is offline   Reply With Quote