جوراب‌ها در تاریکی

چراغ خاموش است و باید در تاریکی لباس بپوشم. کشو ده جوراب سیاه و ده جوراب سفید دارد، همه قاطی. دو جوراب هم‌رنگ می‌خواهم؛ هر رنگی باشد فرقی ندارد.

تاریکی است. کشو $\mathrm{۱۰}$ سیاه ($B$) و $\mathrm{۱۰}$ سفید ($W$) دارد، $|B|+|W|=\mathrm{۲۰}$. دو جوراب هم‌رنگ می‌خواهم.

$|B|=|W|=\mathrm{۱۰}$؛ کمترین $n$ برای دو تای هم‌رنگ.

چند تا بردارم تا مطمئن باشم؟ یکی که بردارم، سیاه است یا سفید. دومی ممکن است فرق کند. سومی حتماً با یکی از دو تای اول هم‌رنگ است، چون فقط دو رنگ داریم و سه جوراب. پس سه تا کافی است و دو تا کافی نیست.

با $n=\mathrm{۱}$ هر رنگی ممکن است. با $n=\mathrm{۲}$ ممکن است فرق کنند. برای $n=\mathrm{۳}$ تعداد جوراب‌ها بیشتر از رنگ‌هاست ($\mathrm{۳}>\mathrm{۲}$)، پس دو تا هم‌رنگ‌اند (اصل لانهٔ کبوتر). پس $n=\mathrm{۳}$ کافی است و $n=\mathrm{۲}$ نه.

$f:\{\mathrm{۱},\mathrm{۲},\mathrm{۳}\}\to \{B,W\}$ پس $\exists s\ne t,f(s)=f(t)$.

اگر دو جوراب سیاه بخواهم چه؟ حالا می‌توانم مدت زیادی بدشانس باشم: ممکن است هر ده جوراب سفید اول بیاید. فقط بعد از آنها هر جوراب حتماً سیاه است، و من دو تا سیاه می‌خواهم: دوازده جوراب.

برای دو سیاه، بدترین حالت این است که اول هر $\mathrm{۱۰}$ سفید بیاید و بعد $\mathrm{۲}$ سیاه، یعنی $\mathrm{۱۰}+\mathrm{۲}=\mathrm{۱۲}$ جوراب.

برای دو سیاه $n_B=\mathrm{۱۰}+\mathrm{۲}=\mathrm{۱۲}$.

شگفتی: با سه رنگ جوراب چهار تا لازم داشتم و با ده رنگ یازده تا. همیشه یکی بیشتر از شمار رنگ‌ها.

برای $k$ رنگ به $k+\mathrm{۱}$ جوراب نیاز است، مثلاً $k=\mathrm{۳}\Rightarrow n=\mathrm{۴}$ و $k=\mathrm{۱۰}\Rightarrow n=\mathrm{۱۱}$.

$n_k=k+\mathrm{۱},n_{\mathrm{۳}}=\mathrm{۴},n_{\mathrm{۱۰}}=\mathrm{۱۱}$.