I am headed back from Scotland today, currently sitting in the Frankfurt Airport after having woken up at 3am to catch my 6am flight.
Scotland had their daylight savings time start (or end, I can never remember which it is) on Sunday. Since I am heading back to the U.S. today, I get to go through our own DST change next weekend as well. This all means 2 things:
- I have no idea what time it is. My watch says 11am, my body says what the hell are we doing, and the wine I'm drinking says vacation isn't over yet.
- I'm feeling ready for winter. I think there will be snow on the ground when I get home. As a result, this problem felt really fitting.
Since I am away from home, I don't have my dog to talk with. Normally she is my rubber duck for algorithms. Instead, I have my Rithm duck standing in as my travel-sized, actual rubber duck. He is as of yet unnamed. I'm still determining his personality.
Okay, sorry for the long intro. I'm a little delirious at this point.
The Problem
Like before, this comes from Algorithmic Puzzles by Maria and Anany Levitin:
Glove Selection
There are 20 gloves in a drawer: 5 pairs of black gloves, 3 pairs of brown,
and 2 pairs of gray. You select the gloves in the dark and can check them
only after a selection has been made. What is the smallest number of gloves
you need to select to guarantee getting the following?
(a) At least one matching pair
(b) At least one matching pair of each color
Solving Process
When I was first learning coding, I heard that children are often better at solving algorithms than adults because we focus on how to solve the problem rather than just solving it. In coding, this means we often focus on what code we will write -- should this be a for loop, is recursion a good choice here, etc. -- instead of just thinking the problem through.
Obviously that isn't an issue here. This book isn't about code at all. But I still found the concern about how to solve getting in the way of solving. I wanted to be sure I was using the right strategy from the book's tutorial.
That was the opposite was of what I was looking to accomplish by going through these puzzles, however, so I decided to forget about strategies and just think it through in the way that felt most natural. When I had a solution, I could assess what method I had used and if there was a better approach.
Forgetting About Pairs
I initially solved an easier but still common version of this problem using colored balls. This means that a pair can consist of any two balls of the some color and there is no need to have a left handed and right handed glove. I took this approach because I forgot that gloves are not interchangeable like socks. My bad. It's been like eight months since I had to wear gloves.
When you don't have to worry about left and right, choosing pairs can took like this:
- First matching pair This puts us at 4 balls as our worst case. If we were to pick a different color on our first three picks and had 3 colors, the 4th pick must be a match.
- Pair of each color. This gives us 18. Because we could pick the 10 black balls, then all 6 brown balls, then the next would have to be grey.
Solving for Left and Right Gloves
After my initial simplification, the actual problem becomes easier since I already know how to think about it. When we add in the constraint of needing a left and right glove to complete a pair, our worst case scenario can look like this:
- First matching pair The answer is 11 because we could, for instance, pick all the left handed gloves of every color first, at which point the next glove must be match.
- Pair of each color Here the answer is 19 because we could theoretically choose all the black gloves, all the brown gloves, and then both the left handed grey gloves as our first 18 choices, making the 19th the first grey pair.
This is a worst case scenario approach and I do not immediately see a simpler way to solve it (nor does the book provide one) outside of simply adding up all of the options. It's not hard or terribly inefficient, but I could see it becoming unwieldy with large numbers of different colors.