Thread: Pigeon hole principle

I understand what the pigeonhole principle is.

if there are n pigeons and m holes than at least one hole has more than n/m pigeons.

But how do I show it with specific example?

a.Suppose a programmer wrote 1000 lines of code in 30 days. Show that there must be at least one day when the programmer wrote more than 33 lines of code.

b.If n is a positive integer, how many distinct integers from 0 to 3n must you pick to be sure of getting a multiple of 3 (0 is considered a multiple of 3).
Hint: try it first with n = 1, 2, 3.

edit: for a. I just put

1000=30*33+10

so if all 30 day have 33 lines of code, there are still 10 lines of code to add to one day, therefore at least 1 will be greater than 33.

I think your answer for 1) is fine. If you were to precisely apply the pigeonhole analogy, you could think of there being 30*33 total holes and 1000 pigeons, but obviously you understand the concept.

For 2), when you range from 0 to 3n, there are going to be numbers that are divisible by 3, and numbers that are not.

For instance, when n=2

0,1,2,3,4,5,6

0; 3,6 are multiples of 3
1,2; 4,5 are not
(notice the groupings)

I can supply a proof if you'd like, but it's intuitively clear and I don't know if you need it.

Once you know this, you know you have "holes", so you need "pigeons" before you are forced to pick a multiple of 3.

thank you!

edit:

I am getting more confused now.

the question askes

Suppose you have the set of integers {1, 2, 3, ..., 19}. How many members of that set must be chosen so that at least two of them sum to exactly 20.

I can see then answer is 11. But what exactly do I need pigeon hole principle to come upon this answer?

I can get then answer but they ask "Use the pigeon hole principle for these questions."

No clue what that means.

edit:

then this one i have no clue how to even begin.

How many distinct integers from 1000 to 9999 inclusive must you pick in order to be sure of getting two that have a digit in common. For example, 1234 and 3038 have the digit 3 in common.

Sorry I didn't get this until now. It doesn't email me to alert me that a reply has been edited.

You often don't "need" the pigeon-hole principle; it is just a nice way to think about things sometimes. In your first problem, there are 10 "holes" that can be filled up before you get a pair that adds to 20; thus you need to find out how many pigeons "force" a pair, and, as you said, the answer is 11.

In the second problem, the restriction (1000 to 9999) forces you to pick 4-digit numbers. Thus you have 10 holes (different digits), and you need to see how many numbers does it take to fill a hole more than once (sharing a digit). The answer is 3 numbers, which means that you have 12 "pigeons" trying to fit into 10 "holes", and thus one of the holes must contain two pigeons.

For instance, your first number could be 1234, and your second number could be 5678. The third number could have a 9 and 0 in it, but then would be forced to include one of the other digits.

Ok ya I understand it. It seems so clear when you explain it. Then I move on to the next question, and my mind can't apply it to the new scenario. When you explain it, it seems clear as day LOL.

Come see me after class.

Originally Posted by Kockay

Come see me after class.

Thats not how you spell my name

LMAO you guys are funny!!!!