Match MakerDiscrete Mathematics Level 3
You have 10 men and 10 women. Each man is married to one of the women (and no woman is married to more than one man). However, you don't know who is married to who; your job is to determine this.
To do this, you make several attempts. In an attempt, you match each man with some woman such that each woman is paired with exactly one man. Then, you are told which couples you guessed correctly. If you haven't guessed all couples correctly, you make another attempt. You repeat this until you get all correct.
Because you don't know anyone, your strategy is simple. You pick the couples at random. When you get a couple correct, in all future attempts, you will pair up that couple. For the other incorrect couples, you guess them at random again; this might mean you repeat a couple you previously attempted.
On average, how many attempts does it take for you to get all couples correct?