0
$\begingroup$

There are 10 red, 8 blue, 8 green & 4 yellow pencils inside a box.

How many pencils must be selected at least, so we can be sure that there is one pencil of each colour among them (selected pencils)? Suppose, that we selected pencils in dark.

This exercise is selected to be done by the Generalized pigeonhole principle.

But, I can´t find way to apply rule of the Generalized pigeonhole principle, which says that

for minimum number of objects (N), at least (r) of them, must be in one of (k) boxes, when these objects are distributed among the boxes

in words that least r number of object must be in one of k boxes. I think instead of one, there should be all of boxes.

The number of selected objects (pencils) N, that we have to select among total of 30 pencils is unknown.

r is 1 (because we have to find one pencil of each colour among them).

Number of boxes (k) is 4 (one for each colour).

So, how to find N ?

Thank you.

$\endgroup$
3
  • $\begingroup$ To be sure, we'd need to select at least $27$ pencils... $\endgroup$
    – MathIsNice1729
    Jan 14, 2016 at 17:09
  • $\begingroup$ Yes, I know final result, but how to calculate it using this principle? $\endgroup$
    – user284901
    Jan 14, 2016 at 17:13
  • $\begingroup$ It's simple logic... You can check out the proof of the generalized PHP... $\endgroup$
    – MathIsNice1729
    Jan 14, 2016 at 17:18

3 Answers 3

Reset to default
2
$\begingroup$

Don't be caught up in the definition - think of it using basic logic. Come up with a worst-case scenario. We could draw the $10$ red pencils, followed by the $8$ blue pencils, followed by the $8$ green pencils, and without ever drawing a yellow pencil, we have already used $10 + 8 + 8 = 26$ moves. But we still need one more draw to get all the colors. Our answer is thus $26 + 1 = \boxed{27}.$

$\endgroup$
6
  • $\begingroup$ Yeah... This is how I thought too... But, the OP said that he wanted to apply the generalized PHP, so I thought he already knew the result this way... $\endgroup$
    – MathIsNice1729
    Jan 14, 2016 at 17:14
  • $\begingroup$ This same logic is the origin of the theory although... $\endgroup$
    – MathIsNice1729
    Jan 14, 2016 at 17:15
  • $\begingroup$ There would be no reason to get bogged down in definitions when common sense will get him directly to the answer. @Sayantan Santra $\endgroup$
    – K. Jiang
    Jan 14, 2016 at 17:16
  • $\begingroup$ Yeah... I agree... But, it bothered me... So I commented instead of answering... :P $\endgroup$
    – MathIsNice1729
    Jan 14, 2016 at 17:17
  • $\begingroup$ A different Q: 10 black socks,10 white socks in a drawer. How many do you need to take to obtain a matching pair? A: 3. $\endgroup$
    – DanielWainfleet
    Jan 14, 2016 at 17:32
1
$\begingroup$

number of boxes I believe should be 27, as you need to choose at least 27 pencils to guarantee one of each, lets look at it like this in the worst case you have after 26 choices, 10 reds, 8 blue, 8 green for 26, this you need to draw 1 more ball with a 100% chance of getting yellow (as no others are left), any other combination less than 27 then would not guarantee you have one of each at least

$\endgroup$
0
$\begingroup$

The total of any 3 pencils is at most 26 .Select 27. At least 1 of them cannot be in the pigeon-holes of any 3 of the colors.So 27 is sufficient.26 is insufficient to apply the principle as there may not be 1 "hole" (yellow) in the selection.So at least 27 is also necessary.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .