抽袜子配对

Pair of Socks

专题: Discrete Math / 离散数学
难度: L2
来源: Brainstellar

题目详情

一个抽屉里有 10 双红袜子和 10 双蓝袜子（共 40 只袜子）。你在黑暗中随机抽取袜子。

问：至少抽多少只，才能保证一定能凑出一双同色袜子？

There are 10 black socks and 10 red socks in a cupboard. Your task is to draw a few socks at random, without looking, such that you get at least one matching pair (single color). What's the least number of socks that you need to draw?

Assume that there is no left-right distinction in these socks.

Hint

Pigeonhole principle

解析

抽 3 只即可保证。

理由：抽两只袜子最坏情况是一红一蓝；第三只无论是红还是蓝，都会与前面某一只同色，从而凑出一双。

Original Explanation

Solution

The Pigeonhole Principle states that if there are $(N+1)$ pigeons to fit in $N$ holes, at least one hole will have $2$ or more pigeons. Hence, if you pick $3$ socks (pigeons) from $2$ colors (holes), at least one color (hole) will have $2$ or more socks (pigeons), i.e. a pair is guaranteed with either red or black color.

In general, if there are $N$ different colored socks, then we would draw $N+1$ socks to ensure at least one matching pair.