Using the pigeonhole principle, formally show that given 100 bins and 100+n ball

Question

Using the pigeonhole principle, formally show that given 100 bins and 100+n balls (0<n<100), if we attempt to allocate the balls in the different bins with a minimum of 0 balls and a maximum of 2 balls per bin, at least n bins will have 2 balls. Using the pigeonhole principle, formally show that given 100 bins and 100+n balls (0<n<100), if we attempt to allocate the balls in the different bins with a minimum of 0 balls and a maximum of 2 balls per bin, at least n bins will have 2 balls.

Explanation / Answer

Pigeonhole principle states that if

n items are put into m containers, with n > m, then at least one container must contain more than one item.

Let us take the first case where we have no empty bins (there is at least 1 ball in every bin) : We first fill 100 balls in 100 bins with 1 ball in each bin. Now we have n balls left and since any box can only have a maximum of 2 balls, therefore, we put those n balls in n different bins. Thus, there are n bins with 2 balls each.

Now, let us take the case where we have some (Let us say k) empty bins. We first fill (100-k) bins with 1 balls each. Now we have n+k balls. Since only a maximum of 2 balls is allowed, therefore, we fill n+k bins with these remaining balls putting 1 in each bin. Thus, here n+k bins have 2 balls.

Thus you can see that minimum of n bins will contain 2 balls when k=0 i.e. the first case.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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