Pigeonhole theorem problem

**Problem #1:**

Suppose N objects are distributed between B boxes in such a way that no box is empty. How many objects must we choose in order to be sure that we have chosen the entire contents of at least one box?

My strategy was to find out the maximum number of contents one box can have, say M.

Then if I choose M objects I can satisfy the given task.

But I'm stuck on finding this maximum number.

I know that by using the pigeonhole principle, I can say *at least one* box has at most or at least some number of contents.

How can I say *all *boxes have at most some number of contents?

**Problem #2:**

There are twelve signs of the Western Zodiac. Suppose there are 145 people in a room. Show that there must be 13 people who share the same sign of the Western Zodiac.

I'm confused about the wording. Is the problem different from "show that there must be at least 13 people who share a zodiac"?

If so, I need hints to find how to narrow down from saying "at least 13 people share one zodiac" to "exactly 13 people share one zodiac".

Re: Pigeonhole theorem problem

in #2 you are splitting 145 objects between 12 groups. Consider the case when the objects are most spread out

Re: Pigeonhole theorem problem

Quote:

Originally Posted by

**Yuuki** **Problem #1:**

Suppose N objects are distributed between B boxes in such a way that no box is empty. How many objects must we choose in order to be sure that we have chosen the entire contents of at least one box?

**Problem #2:**

There are twelve signs of the Western Zodiac. Suppose there are 145 people in a room. Show that there must be 13 people who share the same sign of the Western Zodiac.

I have absolutely no idea what #1 means.

For #2, if there are 12 boxes and 144 balls then if you **put all of the balls** into the boxes **is it possible that each box contains **__at mos__t 12 balls?

Re: Pigeonhole theorem problem

Thank you, I realized where I was stuck on #2.

I thought there had to be some zodiac-subset that had contained precisely 13 people and no more.

But if 15 people had the same zodiac, it would still be true that 13 out of these 15 share the same zodiac, right?

Re: Pigeonhole theorem problem

I believe your method for #1 is correct, when they say choose they mean remove. If no box can be empty then the maximum number in 1 box is N-B+1

Re: Pigeonhole theorem problem

Thanks Shakarri.

So after I put one item in each box so that no box is empty, I have N-B objects left.

If I put all of that in one box, that box will have the max number of contents possible.

Since this box has N-B+1 objects in it, choosing N-B+1, I'm guaranteed to exhaust at least one box?