pigeon hole

The simplest version I can think of is socks in a drawer. Two colors of socks, randomly mixed. You must select three to be sure of having a matching pair.

I think the answer to your question is 13. At twelve, you could have three red, three blue, three green, and three yellow. When you pick the 13th pencil you are assured of having four of the same color.

At thirteen why couldn't you have 10 red and 3 blue?

Guarantee is the key word
You might get 10 red, but in order to guarantee the result, you have to take worst case and that is when you pull equal amounts and need 13.

10 red and 3 blue satisfies the condition of the problem (10 is at least 4).

Ensure is the word


I read this to say that all possible combinations of X pencils must have at least a set of four pencils of the same color.

It is possible to get four matching with only four pulls, but four does not "ensure" four matching. This problem can be restated as "What is the most you can pull without having four matching?" and then add one so that you guarantee a match. If you propose a number less than 13, I will show you a solution that does not have four matching. Don did worst case in his answer to the question.

I'd just got out of the bath when I posted that and my brain was waterlogged.