# Probability question regarding pairs of gloves

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?

• What do you when you say "I can pick up to 4 pairs of gloves of my choice?" Do you get to see the gloves before you pick them? Also what is "a complete matching set?" Do you mean that every glove is matched? If so, do you stop as soon as you're satisfied? Commented Mar 15, 2018 at 3:04
• Yes I get to see the gloves before I pick. A complete matching set means that if I pick 4 pairs of gloves, I will end up with exactly 4 different colors. If I pick 3 pairs of gloves, I will end up with exactly 3 different colors, etc. Commented Mar 15, 2018 at 3:06
• My comment was way off base. That's why I deleted it. Please ignore. Do you know what is meant by the cycle structure of a permutation? Commented Mar 15, 2018 at 3:19
• Yes I understand the concept but have not studied group theory before. The cycle approach makes sense. Commented Mar 15, 2018 at 3:20
• So this can be solved by calculating the probability of there being a cycle of length 4, a cycle of length 3, etc. and then summing them. How would you calculate the probability of there being a cycle of length 4? Commented Mar 15, 2018 at 3:24

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.

• For the case where you have two pairs of cycles of length 5, do you have to divide by 2 since you are double counting? Commented Mar 16, 2018 at 5:12
• ... yes I believe you're right, editting now. Commented Mar 16, 2018 at 5:42

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.)

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...

• I don't think this is what the OP means. See his comment in answer to my comment. I think he's really asking for the probability that a random permutation of 10 elements has a cycle of length 4 or less. Commented Mar 15, 2018 at 3:17