Test by Bikram | Mock GATE | Test 3 | Question: 4

Question

There are coloured pens in a box. $10$ black ones, $8$ blue, $8$ green, $4$ red. With closed eyes, a person picks up some number of pens from the box.

The least number of pens that person needs to pick up to ensure they get at least $4$ pens of the same color is _____.

Answer 1

The problem can be solve with Pigeon Hole Principle. It states that
If you put n + 1 pigeons in n holes then at least one hole would have more than one pigeon.


Consider 4 different colors as 4 holes, now we want to find out the minimum number of pens such that at least one whole contains more than 4 pens.
If we start with 4 holes- black, blue,  green, red.

 Start putting a black , blue, green and red pen  in respective hole. Now each hole has exactly one pen.

 If we repeat this again, then each hole will contain exactly 2 pens.
 Repeat the same third times to have exactly 3 pens in each hole.
 Now if we select a random pen and put in a hole, at least one hole will hold 4 pens, which is what we need .

The total number of pens selected = 4 + 4 + 4 + 1 = 13