Socks Problem: Find the Minimum Number of Days to Guarantee a Matching Pair from a Drawer

Question

## Problem

A drawer contains socks of `k` different colors. You draw socks one at a time in the dark. How many socks must you draw to guarantee at least one matching pair, regardless of the order drawn? Generalize: how many to guarantee `m` matching pairs?

```python
def socks_to_guarantee(colors: int, pairs_needed: int) -> int:
    pass
```

**Example:**
```
colors=3, pairs_needed=1
# Worst case: draw one of each color (3), next must match -> 4
output -> 4  # k + 1 by pigeonhole

colors=3, pairs_needed=2
output -> 5  # k + pairs_needed by pigeonhole extension
```

## Approach

Pigeonhole principle. For 1 pair: `k + 1`. For `m` pairs: `k + m` (in the worst case you have m-1 pairs and one sock of each remaining color; next draw completes an m-th pair).

## Follow-ups
1. The drawer has a limited count of each color: `counts = [3, 2, 1]`. Does the formula change? Derive it.
2. You need `m` pairs of the SAME color, not just m arbitrary pairs. How does the answer change?
3. Extend to a drawer with socks of 2 attributes (color and pattern). Define "matching" as both attributes equal.
4. Turn this into code that also returns which color the guaranteed pair will be in the worst case.

Socks Problem: Find the Minimum Number of Days to Guarantee a Matching Pair from a Drawer

Question Details

Full Details

Topics

More from Square/Block