Socks in a Drawer
Have you ever gone rummaging around in an untidy sock drawer trying to find a matching pair of socks? Maybe you get lucky and the first two socks you pull out are a matching pair. Maybe you manage it after three socks. Sometimes it seems like you've got one of every type before you actually manage to find a matching pair.
But what is the mathematics behind this? What is the maximum number of socks you will need to pull out of the drawer before you are guaranteed to find a matching pair? Let's take a look.
The Simplest Case
The simplest case would be if you only owned one type of sock. Obviously in this example you would only need to pull two socks out of the drawer to be guaranteed a matching pair.
Two Types of Socks in a Drawer
What about if you had two different types of socks in the drawer; red and blue? Worst case scenario is that you pull one colour out on the first attempt and then the other colour on the second attempt. You then pull out a third sock. As you already have one red sock and one blue sock, and this third sock must be red or blue, it is guaranteed to match one of these prior socks. Therefore, for two types of socks, you are guaranteed to get a matching pair in a maximum of three attempts.
Three Types of Socks in a Drawer
What about if you have three different types of socks in your drawer; red, blue and white? This time the worst-case scenario is that after three attempts you have three different socks; one red, one blue and one white. Now on your fourth attempt, there are no further types of socks to pull out, so your fourth sock must be either red, blue or white and hence make a matching pair. Therefore for three socks, you need a maximum of four attempts.
More Socks in the Drawer
By now you should see a pattern starting to form. However many different types of socks you have in your drawer, the worst-case scenario is that you first pull out one of each type of sock. Once you have one of each, you have run out of possibilities, hence your next sock must match one of the types already chosen.
Therefore you are guaranteed to find a matching pair within a number of attempts one higher than the number of types of socks in the drawer.
Mathematically, this means that if you have n different types of socks in a drawer, you are guaranteed to find a matching pair within n + 1 attempts. For example, if you have five different types, you need a maximum of six attempts; if you have 100 different types of socks, you need a maximum of 101 attempts.
Extending the Problem
So far we have only considered what happens when you want a matching pair, but are not concerned about what style they are e.g. it doesn't matter if your socks are red, blue, white etc. as long as they match each other.
What about if you require a particular type of sock? How does this change the problem?
Think back to our drawer of blue and red socks. We have seen that to get a matching pair, we need a maximum of three attempts, but suppose this time we want a pair of blue socks. In this example, the worst-case scenario is that we keep pulling red socks out of the drawer until we run out of them. We are then left with blue socks and so two further attempts will give us a pair of blue socks.
It is a very similar case in our second example with a drawer full of red, blue and white socks. If we wanted a pair of blue socks, the worst-case scenario is that we pull out all of the red socks and white socks, before needing two further attempts to find two blue socks.
Therefore mathematically, if we have m socks in the drawer that do not match the colour we want, we are guaranteed to find a pair of our colour within m + 2 attempts. E.g. if we had 5 red socks, 3 white socks and 6 blue socks, we are guaranteed to find a pair of blue socks in at least (5 + 3) + 2 = 10 attempts. Likewise we are guaranteed to find a pair of white socks in (5 + 6) + 2 = 13 attempts or a pair of red socks in (3 + 6) + 2 = 11 attempts.
This content is accurate and true to the best of the author’s knowledge and is not meant to substitute for formal and individualized advice from a qualified professional.
© 2021 David
David (author) from West Midlands, England on April 24, 2021:
Umesh Chandra Bhatt from Kharghar, Navi Mumbai, India on April 24, 2021: