GATE Civil 2023 Set 2 | GA Question: 4

Question

There are $4$ red, $5$ green, and 6 blue balls inside a box. If $N$ number of balls are picked simultaneously, what is the smallest value of $N$ that guarantees there will be at least two balls of the same colour?

One cannot see the colour of the balls until they are picked.

• A. $4$
• B. $15$
• C. $5$
• D. $2$

Answer 1

The Pigeonhole Principle tells us that if we have more objects to put into boxes than there are boxes, at least one box must contain multiple objects.

In this case, each color (red, green, and blue) can be considered a "box," and the balls we pick are the objects. We want to find the smallest value of $N$ such that we are guaranteed to have at least two balls of the same color.

The worst-case scenario for this problem is when we pick one ball of each color $\text{(1 red, 1 green, 1 blue)}.$ In this case, $N$ would be $3,$ and we still don't have two balls of the same color. However, if we pick just one more ball (regardless of its color), we will have at least two balls of the same color.

So, the smallest value of $N$ that guarantees there will be at least two balls of the same color is $4.$

Correct Answer: A

References:

• https://www.eecs.yorku.ca/course_archive/2008-09/S/1019/Website_files/19-the-pigeonhole-principle.pdf
• https://math.berkeley.edu/~rhzhao/10BSpring19/Worksheets/Discussion%203%20Solutions.pdf
• https://brilliant.org/wiki/pigeonhole-principle-definition/