Re: Pigeon hole principle

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 $\displaystyle n+1$ numbers that are divisible by 3, and $\displaystyle 2n$ 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 $\displaystyle 2n$ "holes", so you need $\displaystyle 2n+1$ "pigeons" before you are forced to pick a multiple of 3.

Re: Pigeon hole principle

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.

Re: Pigeon hole principle

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.

Re: Pigeon hole principle

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.

Re: Pigeon hole principle

Re: Pigeon hole principle

Quote:

Originally Posted by

**Kockay** Come see me after class.

Thats not how you spell my name(Rofl)

Re: Pigeon hole principle

LMAO you guys are funny!!!! :D