On Pigeons and Pigeonholes Professor P. has an odd habit: He only buys red, gree

Question

On Pigeons and Pigeonholes

Professor P. has an odd habit: He only buys red, green, and blue books, and he keeps them in completely unordered stacks. However, he does keep track of the total number of books he owns. One day he decides to get a bookshelf so that he can put all books of one of the colors onto it. Unfortunately, when he is at the shelf store, he only knows that he has a total of 271 books, but he does not know how many books of each color he owns. What is the minimum number of books that the new shelf must be able to hold so that Professor P. can be sure he can put all his books of one of the colors onto it? He does not care which color it will be.

Explanation / Answer

The worst case scenario is when all the books Prof P owns is of only one color, say Red. Assuming that Prof P is contend with keeping all books of Blue color, that is zero in the shelf we proceed to answer the question. In other words we assume that if all the books are of one color then Prof P doesn't use the shelf.

Clearly the set of books, S can be divided into three disjoint subsets, B of blue books, G of green books and R of red books.

Now |R| + |B| + |G| = 271.

Suppose we know |R|, |G| and |B| before-hand. Then to ensure that all books of one particular color goes into the shelf, we only need to ensure the shelf to have the size equal to the minimum among |R|, |B| and |G|. Say the minimum is |B|, then we keep all books of blue color in the shelf.

But we do not know |R|, |G| and |B| before-hand. So we need to find the maximum this minimum can achieve. With out loss of generality suppose |R| >= 92 then clearly one among |G| or |B| has to be less than 90 (|B|+|G| <= 271-92=179. So one of |G| or |B| has to be less than 179/2).

So suppose |R| = 91. Now |B|+|G| = 180. And the maximum possible value the minimum among |R|, |B| and |G| can take in this scenario is 90. Since we already established that any other scenario leads to a lower minimum, this is certainly the greatest of the minimum. Notice that altering the role R, G or B doesn't lead to any other scenario.

Hence if we ensure the shelf has size at least 90, we can be sure of keeping all the books of that color which is minimal in size.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

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