Use the pigeonhole principle to answer the following questions. Give an explanat

Question

Use the pigeonhole principle to answer the following questions. Give an explanation of how you arrived at your answers.

a) A box contains 8 red balls and 8 black balls. A woman takes balls out at random without looking at them. Once a ball is taken out it is not replaced back in the box. How many balls must she select to be sure of having at least three balls of the same color?

b) How many numbers must be selected from the set {1, 2, 3, 4, 5, 6, 7, 8} to guarantee that at least one pair of these numbers add up to exactly 9?

Explanation / Answer

There are 8 red and 8 black balls.

Minimum balls she should select to be sure of atleast two colours is 5

Since if she takes 3, they may be one red and two black or two black and one red

If she takes 4 , then there is a chance that 2 red 2 black.

If she selects 5, then possibilities are (5r,0b) (4r, 1b) (3r, 2b) (2r,3b) (1r,4b) (0r,5b)

Hence in any case she has 3 balls of same colour.

-----------------------------------------------------

Since not given we can assume it is without replacement

pairs adding 9 are (1,8) (2,7)(3,6) (4,5)

Total number of ways of selecting 2 from 8 are = 8C2 = 28

Hence by pigeon hole principle if 28 is partitioned into 7, then there is one chance all the above 4 may be in one group.

Hence she must exhaust 6x4 and 1 from here

i.e. minimum 25 she must select to ensure that atleast one add to 9

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.