Fifty Shades of Gray (Socks)

Heidi has a huge drawer full of gray socks. These socks are all disorganized in a random heap. As the title of this puzzle suggests, there are fifty different shades of gray sock in her collection (it’s assumed that it is a huge pile of socks, so there could be multiple copies of every shade).

Heidi has a great eye for color, but not perfect. She can distinguish the shade of socks only if they differ by two, or more, shades. So, if a pair of socks is in the range ±1 they appear the same color to her.

Heidi’s desire is to find a pair of ‘matching’ socks (two socks that are no more than one unit shade apart) but, unfortunately, she is currently blindfolded (don’t ask). How many socks does Heidi need to take from the drawer to guarantee that she has at least a pair of ‘matching’ socks?

As a bonus, Heidi would like to find a pair of matching socks for her partner too. How many additional socks will she need to pull to ensure that she gets at least two pairs of ‘matching’ socks?

To solve this puzzle, we need to look at the worst possible case. If Heidi is incredibly unlucky with her selections, what is the cruelest collection that can happen? Let’s label the socks [1-50].

The unhealthiest selection she can draw is [1,3,5,7,9 … 43,45,47,49] or the chiral image of [2,4,6,8,10 … 48,50]. If she is unlucky enough to pull socks of this configuration, she will have drawn 25 socks and there will be no socks that are closer than ±1 (she could be lucky and get plenty of matches, but we need the guarantee so need to look at the worst case).

However, once these 25 socks are taken, the next sock pulled must be a ‘match’. It will either match, exactly, to one of those already drawn, or be in one of the gaps between socks she already has. Heidi needs to pull 26 socks to ensure a matching pair.

How about to get two matching pairs? Again, she could probably be lucky, but what is the worst thing that can happen? Starting with 26 socks, the worst that can happen is if she draws another of the same sock. Let’s image she selected [1,3,5 … 47,49] followed by another [1] for her 26th pull. If she is unlucky enough to draw a third [1], it’s not a ‘match’ to anything anymore so she has to draw a further sock to guarantee. Thus, she needs to draw two more socks after the first 26 to guarantee a second ‘match’ for an answer of 28.

That’s a lot of socks!