.
A cold-footed centipede has a drawer filled with many, many socks. And yes, that
centipede does have 100 feet. If the centipede only owns green and brown socks, how
many must it pull from the drawer in the dark of the morning to be assured that it has
a matching set for all of its feet (100 socks of the same color)? What if the centipede
also owns polka-dotted socks? What if the centipede’s drawer has many, many socks
of k different colors?
~~~~~~~~~~~~~~
For 100 feet/socks and 2 (two) colors, like green and brown, the answer is " pull at least 199 socks ".
Then among these 199 socks, at least 100 must be one of the two colors.
---------------
It is a nice and very well known entertainment problem.
See my lesson
- In the worst case
in this site.
Find there many other similar and different solved problems.