Probability question regarding pairs of gloves

Question

I've been thinking about this question but don't know how to approach it. I think there should be 10! ways of the gloves being paired but I'm having trouble after that. Here is how it goes:

I have 10 different pairs of gloves, each of a different color. They are randomly shuffled and paired. Each pair still contains a left and right glove (there are no left-left or right-right pairs). From this newly arranged set of gloves, I can pick up to 4 pairs of gloves of my choice.

I am satisfied if out of these pairs of gloves that I pick, the number of colors is equal to the number of pairs I picked. For example, if I choose to pick 2 pairs of gloves and the first pair is Red/Green and the second pair is Green/Red, then I am satisfied because in the end I have exactly 2 colors and I picked exactly 2 pairs of gloves.

What is the probability that I will be satisfied?

Answer 1

If you randomly decide upon n pairs of gloves, you will be satisfied if the set of left glove colours exactly matches the set of right glove colours. There are 10-choose-n sets of colours of size n, and since each is equally likely, there's a one in 10-choose-n chance of you being satisfied. 10-choose-n is 10!/(n!(10-n)!), so 1/10 for one glove, 1/45 for two, 1/120 for three etc.

If, on the other hand, you specifically search for a set of gloves that will satisfy you, the odds of being satisfied are obviously much higher. Rather than counting ways in which you might be satisfied, it's easier to identify the specific permutations where you will not be satisfied. As a commenter has already stated, it's equivalent to asking what proportion of permutations of 10 things have a cycle of length 4 or less. Think of it this way, you start with one pair of gloves, consider the left glove, and look for the pair with the matching right glove. Keep repeating this until the pair you're looking for next is the pair you started with. You now have a cycle in the permutation, and if it's of length four or less you've found a set of gloves to satisfy you.

Firstly observe that all permutations consist of a disjoint set of cycles. Which means, if a permutation has a cycle of length 8, then the remaining two elements must either be in a cycle of length 2 or two cycles of length 1. So, you will be satisfied if there are any cycles of length 1, 2, 3 or 4, and you will also be satisfied if there are any cycles of length 6, 7, 8 or 9 since all of those force there to be a cycle of length 4 or less in the remaining elements. The only options under which you will be unsatisfied are two cycles of length 5, or one cycle of length 10.

There are:

• 10! permutations in total
• 9! cycles of length 10, thus a 9!/10! = 1/10 chance of this happening
• 10-choose-5.4!.4! / 2 = 10!4!4!/(5!5!2) pairs of cycles of length 5, thus a 1/50 chance of this happening. That's 10-choose-5 choices for the members of the "first" of the cycles, 4! different 5-cycles for each of the two, and dividing by 2 because (as you observed) this counts each pair twice.

Final probability is 1 - 1/10 - 1/50 = 88% of being able to satisfy yourself.

Answer 2

You're correct in that there are $10!$ ways to shuffle the gloves. Now imagine that you pick up the right red glove, and it's paired with the blue left glove. So then you pick up the blue right glove and find it's paired with the green left glove, so you pick up the green right glove and find it paired with the red left glove. Success!

So, the problem is to count the number of permutations of $10$ elements that have a cycle of length four or less. Since any permutation factors into a product of disjoint cycles, there are only two possibilities: one ten-cycle or two five-cycles.

Now how many ten-cycles are there? The red glove has to come somewhere in the cycle. There are $9!$ ways to arrange the gloves, so there are $9!$ ten-cycles.

You take it from here. (By the way, disjoint cycles commute, so it doesn't matter which five-cycle you choose first.)

Answer 3

Basically, you select 4 from 10 left gloves, and 4 from 10 right gloves, and are satisfied if at least two from those selected left gloves match the colours among the selected right gloves.

Let's call a left glove "good" if it matches one from the selected right colours, and "bad" if it does not. You are satisfied if all the gloves you select are good.

So you want the probability that you select 1 right glove and its good left glove, or don't yet have two good left gloves when you select another pair, or don't and have three good gloves when you select a third pair, or don't yet have four good gloves when you select the fourth pair.

Hmmm... well, without loss of generality we can assume the colours of the first four right gloves are predetermined.

Let $S$ be the random variable counting draws until satifaction.

$\mathsf P(S=1) = \frac 1{10}\\\mathsf P(S=2\mid S>1)=\frac{1}{90}$

If you have not been satisfied on the first draw, you will be satified on the second if the first left matches the second right and the second left matchs the first right.

got to go...More to come after I get back...